Take the 2-minute tour ×

I need to resolve this recurrence:

$$T(2^n) = T(2^{n-1}) + 2^n$$

The conditions are:

Give a $\theta$ bound. In case that cannot find a $\theta$ bound, provide tight upper ($O$ or $o$) and lower ($\Omega$ or $\omega$) bounds.

Assume that $T(1) = 1$

Thanks so much!

share|improve this question
You might try to compute the first values of T(2^n) and see whether a pattern emerges (and a pattern does emerge...). –  Did Oct 7 '12 at 19:47
@calbertts, fgp's answer is better, why you accept Robert Israel's answer? –  doraemonpaul Oct 8 '12 at 22:26
@doraemonpaul - sometimes a hint is better than a solution. the OP and him only can decide which answer his better –  Belgi Oct 9 '12 at 2:00

2 Answers 2

up vote 4 down vote accepted

Hint: the recurrence only defines $T$ on powers of $2$. Let $A(n) = T(2^n)$.

share|improve this answer

Look at $\tilde{T}(n) = T(2^n)$. The recurrence for $\tilde{T}$ is then $$\begin{eqnarray} \tilde{T}(n) &=& \tilde{T}(n-1) + 2^n \\ T(0) &=& 1. \end{eqnarray}$$

It follows that $\tilde{T}(n) = 1 + 2 + 4 + \ldots + 2^n = 2^{n+1} - 1$ and thus that $T(n) = 2^{\log_2(n)+1} - 1 = 2n - 1$ (if $n$ is a power of two, your recurrence doesn't define $T(n)$ for other values of n). A possible $\theta$-bound for $T$ is thus $n$, i.e. $T(n) \in \theta(n)$. Note that this assumes that $T(n)$ where $n$ isn't a power of two (a case which your recurrence doesn't define!) obeys the bound (derived soley from the power-of-two values) also. A natural assumption which guarantees that is $T(n) \leq T(n+1)$.

share|improve this answer

Your Answer


