-3
$\begingroup$

I am not able to solve time complexity analysis of this recurrence relation: T(n)=3T(n/2)+n^2.I want to find time complexity analysis of this recurrence relation without using masters theorem could you please help me to do so.

$\endgroup$
1
  • $\begingroup$ Do you want to solve the recurrence or analyse the runtime of evaluating it? What have you tried and where did you get stuck? $\endgroup$
    – Raphael
    Aug 20 '15 at 15:27
1
$\begingroup$

Imagine your recurrence as a tree. It has a height of $log_2(n)$ since your input size $n$ is divided by $2$ every time.

The cost for a node on the $ith$-level is $(\frac{n}{2^i})^2$.

On the $ith$-level there are $3^i$ nodes.

The cost for that level (whithout considering the childnodes) ist therefore $3^i*(\frac{n}{2^i})^2$

The overall cost is the sum of the cost for each level that is $\sum_{i=0}^{log_2(n)} (3^i*(\frac{n}{2^i})^2) = \sum_{i=0}^{log_2(n)} (3^i*\frac{n^2}{2^{2i}}) = n^2*\sum_{i=0}^{log_2(n)} (\frac{3^i}{2^{2i}}) = n^2*\sum_{i=0}^{log_2(n)} (\frac{3^i}{4^{i}}) = n^2*\sum_{i=0}^{log_2(n)} (\frac{3}{4})^i$.

Which you can now solve with a formula for a geometric series that gives you $4n^2-3^{log_2(n)+1}$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.