0
$\begingroup$

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!

  • 0
    @doraemonpaul - sometimes a hint is better than a solution. the OP and him only can decide which answer his better2012-10-09

2 Answers 2

4

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

1

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