QUESTIONS

Find the order of growth of the following recurrence relations using the Substitution Method.

a$.T(n)=T(\frac{n}{3})+T(\frac{2n}{3})+1$

b$.T(n)=3T(\frac{n}{2})+O(n)$

Find the order of growth of the following recurrence relations using the Master Method.

a$.T(n)=9T(\frac{n}{3})+n$

b$.T(n)=3T(\frac{n}{4})+nlgn$

Can the master method be applied to the following recurrence? Why or why not?

$T(n)=4T(\frac{n}{2})+n^{2}lgn$