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

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?

## migrated from stackoverflow.comApr 30 '13 at 14:34

This question came from our site for professional and enthusiast programmers.

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)$.
• This doesn't look very rigorous. If we have $S(n) = n + \log n + \log n + \ldots + \log n$ with $n$ terms of $\log n$, then the "highest power" is $n$ but the complexity is not $O(n)$. – TMM Apr 30 '13 at 14:41