Recurrance Relation - Recursion Tree

Question

On solving the Recurance

T(n) = 3T(n/4) + cn2

I was stuck at summation

$\sum_{i=0}^{log_4 n} (\frac{3}{16})^{i} cn^{2}$

Can someone could help ?

Comments

use simple G.P sum formula i.e a(1-rⁿ)/1-r where a is first term, r common ratio and n is no of terms.

In your question a=1, r=3/16 and n = log₂n ... in solving this you will reach (3/16)^log₂n ...you can handle this via using an important log property i.e a^log_bc = c^log_ba . 

Answer 1

$\sum_{i=0}^{log_4 n} (\frac{3}{16})^{i} cn^{2}$

$\Rightarrow cn^2\Bigg [ 1 + \frac{3}{16} + \frac{3}{16}^2 + \dots + \frac{3}{16}^k \Bigg]$ ($\color{green}{k = log_4n}$)

$\Rightarrow \large cn^2 \Bigg [ \frac{1 - (\frac{3}{16})^{log_4n + 1}}{1 - \frac{3}{16}} \Bigg ]$

$\Rightarrow \frac{16}{13}cn^2 \Bigg [ 1 - (\frac{3}{16})^{log_4n}*\frac{3}{16} \Bigg ]$

$\Rightarrow \frac{16}{13}cn^2 \Bigg [ 1 - n^{log_4\frac{3}{16}}*\frac{3}{16} \Bigg ]$

$\Rightarrow \frac{16}{13}cn^2 \Bigg [1 - n^{log_43 - 2}*\frac{3}{16} \Bigg ]$

$\Rightarrow \large \frac{16}{13}cn^2*\Bigg [\frac{16-3*\frac{n^{log_43}}{n^2}}{16} \Bigg ]$

$\color{navy}{\large \Rightarrow \frac{c}{13} \Bigg [ 16n^2 - 3n^{log_43} \Bigg ]}$

Comments

I didnt understand the 2nd last step. How did u cancelled out 3/16 ?

---

I wrote $n^{log_43} - 2$ as $\frac{n^{log_43}}{n^2}$. and then simplified.

---

See now:)

---

I got that . But there is 3/16 term right ?

---

Yes, There was typing mistake then, now it's corrected.

$\large T(n) =  \frac{c}{13} \Bigg [ 16n^2 - 3n^{log_43} \Bigg ]$

---

Understood :)  Thank you so much :)

Answer 2

---

NOTE: 

• No need to do this calculation 
• With $\text{ratio} < 1$ a sum of $GP$ series evalutes to $\Theta(1)$

Answer 3

why dont you use MASTER theorem it is  fast method

answer   : ⊜ (n²)

Comments

Because I want to learn Recursion Tree Approach .

Answer 4

You should Use directly Master's Algo in this type of Questions

a=3,b=4,k=2,p=0

a<b^k

Complexicity = O(n²log⁰n)=O(n²⁾