Question # $2$: Solve the following recurrences using Substitution method.

i$.$ T$($n$)=$ T$($n$/3)+$ T$($n$-3)+$ n

ii$.$ T$($n$)=($n$/8)$ T$($n$/8)+$ lgn

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

iv$.$ An $=2$An$2+$ lgn

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

Question # $3$: Solve the following recurrences using Recursion tree method.

i$.$ T$($n$)=2$T$($n$/4)+$ n$^2$

ii$.$ An $=2$An$/4+$ n$/2$

iii. T$($n$)=$ T$($n$/4)+$ T$($n$/6)+$ n

iv$.$ Fn$=$ Fn$4+2$n

v$.2$an$/4=$ an $$ an$/2$ n$/2$

Question # $4$: Solve the following recurrences using Master method.

i$.$ Fn $=4$Fn$/8+$ n$^2$

ii$.$ T$($n$)=4$T$($n$/8)+$ n$^2.$lgn

iii. T$($n$)=2$T$($n$/2)+3$T$($n$/3)+$ n$^2$

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

v$.$ An $=2$An$/3+$ n$^3$