1

$T(1) = 1 $ ,

$T(n) = 3T(\sqrt[3]{n}) + \log_{2}(\log_{2}n)$.

I tried to define $ n = 2^{k}$.

So, $T(2^k) = 3T(2^{\frac{k}{3}}) + \log_{2}k$

Then defin $S(k) = T(2^k)$

So ,$S(k) = 3S(\frac{k}{3}) + \log_{2}k$

And now im pretty stuck, Someone has an idea ? Thanks.

Community
  • 1
NM2
  • 721

1 Answers1

0

You have solved $S(k) = 3S(\frac{k}{3}) + \log_{2}k$

Now, you can use master theorem case $(1)$ :

$T(n)=a\;T\!\left({\frac {n}{b}}\right)+f(n) \space\text{where}\space > {\displaystyle a\geq 1{\mbox{, }}b>1} $

If ${\displaystyle f(n)=O\left(n^{c}\right)} $ where ${\displaystyle > c<\log _{b}a} $ (using big O notation)

then:

${\displaystyle T(n)=\Theta \left(n^{\log _{b}a}\right)} $

You have $a=3$, $b=3$, and $f(k)=\log_2{k}$

Therefore,

$f(k)=O(k^{\log_3{3}})$

$\implies \log_2{k}=O(k)$

Hence, $S(k)=\Theta(k)$

Putting back $n=2^k$, we get

$T(n)=\Theta(\log_2{n})$

Mithlesh Upadhyay
  • 4,787