Solve the following recurrences using Substitution method.

i$.$ T$($n$)=($n$-1)$ T$($n$/8)+$ n

ii$.$ An $=$ An$1+2$An$2+2$n

iii. An $=2$ An$2+$ lgn

iv$.$ T$($n$)=$ T$($n$/4)+$ T$($n$/2)+$ n