Take the 2-minute tour ×
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.

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
2  
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
add comment

2 Answers

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
add comment

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
add comment

Your Answer

 
discard

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.