Writing a tight bound for a recurrence relation

94 Views Asked by At

$$\begin{align}T(n) &= 2 \cdot T(n-1) + 1\\ &= 2^2\cdot T(n-2)+2+1\\ &= 2^3\cdot T(n-3)+2^2+2+1\\ &= 2^4\cdot T(n-4)+2^3+2^2+2^1+2^0\end{align}$$

general form: $2^n\cdot T(0) + 2^{(n-1)} + 2^{(n-2)}\cdots +1$

Is this correct? Also, my friend said the general form has big Theta of $(2^n)$. Cans someone please explain why without advanced math (in layman's terms because I am slow.) THankyou very much!!!

1

There are 1 best solutions below

0
On

Looks right to me.

As for the asymptotic behavior; collecting the $T$-less terms gets you

$$\begin{align}T(n)&=2^nT(0)+2^n-1\\ &=2^n\left(T(0)+1\right)-1\end{align}$$

And since $T(0)$ is a constant, you have $T(n) = 2^nk-1$, which clearly gives $\Theta(2^n)$: for large enough $n$, it's bounded above by $2^nk$, and below by $2^n(k-\epsilon)$, where $\epsilon$ is an arbitrarily tiny number.