0
$\begingroup$

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?

$\endgroup$

migrated from stackoverflow.com Apr 30 '13 at 14:34

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

0
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – TMM Apr 30 '13 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.