ISI2011-PCB-CS-3a

Question

Solve the following recurrence ($n$ is a natural number):

$$T(n) = \begin{cases} 7T(n\div3)+n^2 & ;n>2 \\ 1 & ;n \leq 2. \end{cases}$$

Answer 1

According to Masters Theorem

a = 7

b = 3

k = 2

so it's case of a < b^k

($N^2$) will be complexity.

Answer 2

$T(n)=7T\left ( \frac{n}{3} \right )\dotplus n^{2}$

Given recurrence relation is in this below form.

$T(n)=aT\left ( \frac{n}{b} \right )\dotplus n^{c}$

Solving this recurrence relation we get,

$T(n)=n^{c}\sum_{k=0}^{log_{b}n-1} \left ( \frac{a}{b^{c}} \right )^{k}\dotplus n^{log_{b}a}$

And geometric sum,

$\sum_{k=0}^{n}x^{n}= \frac{x^{n+1}-1}{x-1}=\Theta \left ( x^{n} \right )$

Now after solving  the given relation we get

$T(n)=n^{2}\sum_{k=0}^{log_{3}n-1} \left ( \frac{7}{3^{2}} \right )^{k}\dotplus n^{log_{3}7}$

And the sum of decreasing  geometric term $\sum_{k=0}^{log_{3}n-1} \left ( \frac{7}{3^{2}} \right )^{k}$ will be constant.

So $T(n)=n^{2}\dotplus n^{log_{3}7}$

$T(n)=O\left ( n^{2} \right )$

Comments

I guess question asks for exact solution.

Answer 3

order of n^2

Answer 4

by expanding function:-

T(n) = 7T(n/3) + n²    

         = 7(7T(n/3²) +(n/3)²)+n²

         = 7^kT(n/3^k) +(n/3^k-1)² +.......n²      n/3^k =1  =>  log₃ n = k

T(n) = n² [7/9 + (7/9)² + (7/9)³ ...........(7/9)^k ]

T(n) = n² [7/9 + (7/9)² + (7/9)³ ...........(7/9)^{(log₃ n) -1} + (7/9)^{log₃ n} ]

T(n) = n²(7/9 - (7/9)^{(log₃ 7/9) +1})/(1 - 7/9)        (7/9<1)