Solve the recurrence $T(n) = T(\log_2 n) + 13n$

Question

I have the following recurrence relation $$T(n) = T(\log_2 n) + 13n.$$

I believe in order to solve the equation I need to determine the height of the tree.

$$T(n) \to T(\log_2 n) \to T(\log_2(\log_2 n)) \to \ldots \to T(0)$$

I feel it's very efficient, but how do I compute/prove it? I would like to know the closed form of this recurrence relation. Any suggestions?

Answer 1

The problem can be solved by expanding the recurrence relation as you have suggested. The recurrence relation is $T(n) = T(\log_2 n) + 13n$.

$$\begin{align} T(n) &= T(\log_2 n) + 13n \\ T(n) &= T(\log_2 \log_2 n) + 13\log_2 n + 13n \\ T(n) &= T(0) + \ldots + 13 \log_2 \log_2 n + 13 \log_2 n + 13n\end{align}$$

The term with highest power is $13n$. From which we can conclude that the complexity of the recurrence is $O(n)$.