Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
up vote 4 down vote accepted

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

share|cite|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|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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