edited by
1,138 views
2 votes
2 votes
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 ?
edited by

4 Answers

5 votes
5 votes
$\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 ]}$
edited by
4 votes
4 votes


NOTE: 

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

why dont you use MASTER theorem it is  fast method

answer   : ⊜ (n2)

0 votes
0 votes

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

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

a<bk

Complexicity = O(n2log0n)=O(n2)

Related questions

3 votes
3 votes
2 answers
1
Diksha Aswal asked Jul 3, 2017
1,859 views
T(n) = T(n/3)+T(2n/3)+n What is the solution of Above Given recurrence relation?Give full method to solve this
3 votes
3 votes
2 answers
3
pC asked Jan 15, 2016
497 views
an = an-1 + n , n>=1a0=2Find a100... ?SolutionI actually wanted to know what is wrong with this method .Could you pls help Whats wrong here .T(n) = T(n-1)+nand back su...
1 votes
1 votes
2 answers
4