What Recursion is This?

Computer Science Level 3

$\large T(n) = 16T(\lfloor \sqrt[4]{n} \rfloor) + \log ^{2} (n)$

Upon analyzing a function's time complexity, the above relation came up. Then what does $T(n)$ belong to?

Notations: $\mathcal{O},$ $o$ , $\Omega$ , $\omega$ and $\Theta$ are standard Landau notations .

\omega(n)

\Theta(n\log(n))

\mathcal{O}(\log^{2}(n)\log(\log(\log(n))))

\mathcal{o}(n^{4}\log^4(n))

\Omega(n^{2}\log^{3}(n))

3 solutions

Kunal Gupta
Sep 20, 2017

At first , the recurrence might be a bit overwhelming, but if we look at it by changing variables, we can see more easily! So let $m = \log(n)$ . So that the recurrence becomes: $T(2^{m}) = 16T(\lfloor 2^{\frac{m}{4}} \rfloor)+ m^{2}$ Now, let another recurrence variate $R(m) = T(2^m)$ . So that we have , $R(m) = 16R(\dfrac{m}{4})+m^{2}$ Now, we'll apply Master Theorem to solve this recurrence. We have, $R(m) = \Theta (m^{2}\log(\log(m)))$ Plugging $m = \log (n)$ we get: $T(n) = \Theta(\log^{2}(n)\log(\log(\log(n))))$ As, $\Theta(n) = \mathcal{O}(n)$ So, $T(n) \in \mathcal{O}(\log^{2}(n)\log(\log(\log(n))))$

You use wrong notation for log(logn) , means (logn) power2 is different from log(logn).

ISHAN TYAGI - 3 years, 6 months ago

Hey, in my opinion everything is correct. $\log^{2}(n) = (\log(n))^{2}$

Kunal Gupta - 3 years, 6 months ago

Won't Master theorem give (m^2)logm as the answer to the new recurrence

NILAY PANDE - 3 years, 6 months ago

No, check your working again, the answer given is correct

Kunal Gupta - 3 years, 6 months ago

Vikas Venkatraman
Nov 24, 2017

use recurrence tree to solve the problem... when you sketch the recurrence tree for the above problem,you will find that, at every stage log^2(n) work is been done and the height of the recurrence tree is log(log(log(n))). so T(n)=O( log^2(n)log(log(log(n)))) is the correct answer.

Hasmik Garyaka
Sep 20, 2017

I don't know what mean $mathcal{O}$ but other choices are wrong and I did as Sherlock Holmes.

What Recursion is This?

3 solutions

0 pending reports