0

I'm having trouble deciphering what this recurrence relation is: $$T(n) = T(n^\frac13) + \log n$$ when I try to expand it out I get: $T(n) = T(n^\frac1{3^k}) + k\times\log n $

my problem is breaking down or converting what the big oh notation is, I've seen examples for substituting $n=2^k$ but I don't think that works here. and solving $n^{\frac1{3^k}}=0$ doesn't look right to me.

Joshhw
  • 603

2 Answers2

0

NOTE

This answer is faulty! Sorry for that! See comment section.

You can write $$ T(n^3)=T(n)+3\log n $$ and then substitute $n=2^k$ to have $$ T(2^{3k})=T(2^k)+3k\log 2 $$ and finally substitute $k=3^m$ to have $$ T\left(2^{(3^{m+1})}\right)=T\left(2^{(3^m)}\right)+3^{m+1}\log 2 $$ From which we are able to deduce recursively that $$ \begin{align} T\left(2^{(3^{m+1})}\right)&=T(2)+(3^{m+1}+3^m+...+9+3)\log 2\\ &=T(2)+\frac{3^{m+2}-3}{3-1}\cdot\log(2) \end{align} $$ and so for large values of $n=2^k=2^{(3^{m+1})}$ corresponding to $m=\log_2(\log_3(n))-1$ or equivalently $m=\log_3(\log_3(n)^{1/\log_3(2)})-1$ we have $$ T(n)\approx \frac{3^{m+2}}2\cdot\log 2=\frac{3}{2}\cdot \log_3(n)^{1/\log_3(2)}\cdot\log 2 $$ Since $1/\log_3(2)\approx 1.5849625$ it appears that we must roughly have $$ T(n)\in\Theta((\log n)^{1.5849625}) $$ so this is slightly faster than mere logarithmic growth - if I am not mistaken.

String
  • 18,395
  • actually there is a small issue i can see in this: let $y = 2^{3^{m+1}}$ then $m = \log_3 ( \log_2 (y))) - 1$

    which means $T(y) \approx \frac{\left(3\cdot\log_{2}\left(x\right)-3\right)}{2}\cdot\ln\left(2\right)$

    from which $T(n) \in \mathcal O (ln(n))$ would follow, with a constant of 3/2 ln(2)

     – Control May 14 '23 at 16:23
  • @Control I am afraid your a right! Since $F(n)=ln(n^a)$ yields $F(n)\in\mathcal O (ln(n))$ and $G(n)=ln(n)$ yields $G(n)\in\mathcal O (1)$ we surely have $T(n)=aF(n)+bG(n)\in\mathcal O (ln(n))$. Sorry for this confusion! – String May 20 '23 at 10:41
0

With $a>0$ we have $n = a^{\log_a n}$ then

$$ T\left(a^{\log_a n}\right)=T\left(a^{\log_a n^{\frac 13}}\right)+\log_a n $$

or calling $z = \log_a n$ this recurrence can be recast as

$$ R(z) = R\left(\frac z3\right)+z $$

now calling $z = 3^m$ the recurrence can again be recasted as

$$ S(m)=S(m-1)+3^m $$

with solution

$$ S(m) = \sum_k^m 3^k + c_0 = \frac 12(3^{m+1}-1)+c_0 $$

and now going backwards with $m=\log_3 z$ and $z = \log_3 n$ we have

$$ T(n) = \frac 12\left(3\log_3 n-1\right) + c_0 $$

Cesareo
  • 33,252