Asymptotic Analysis prove that

Question

For $n \geq 1$, consider the following recurrence relation $$T(n) = \log2 n + T(n1/3).$$ Prove that $$T(n) = O(\log_2 n)$$

Answer 1

I'm assuming $n1 = n$? The question is a little unclear but that's okay:

Let $T(n) = log_2(n) + T(\frac{n}{3})$

Let us start expanding out this recurrence relation:

$$T(n) = log_2(n) + log_2(\frac{n}{3}) + T(\frac{n}{9})$$

Continuing this process:

$$T(n) = log_2(n) + log_2(\frac{n}{3}) + \text{ ... } + log_2(\frac{n}{3^k})+T(\frac{n}{3^{k+1}})$$ Where $ \frac{n}{3^{k+1}} \leq 1$

$$\implies T(n) = log_2(n*\frac{n}{3}*...*\frac{n}{3^k}) +T_0$$ This follows directly from logarithm rules.

Now by applying more logarithm rules, we deduce the following:

$$T(n) = log_2(\frac{n^{k+1}}{3^{1+2+...+k}}) +T_0 = (k+1)log_2(n) +T_0 -log_2(3^{1+...+k}) \in O(log_2(n))$$

Hope this helps oof.