What is the complexity of T(n) = 2*T(n/2) + 1, Given T(1) = 1

Question

I attempted to solve this using substitution ->

T(n) = 2*T(n/2) + 1

T(n/2) = 2*T(n/4) + 1

Eventually I get to:

(2^3)T( n/8 ) + 2^2 + 2^1 + 2^0

Or

(2^i)T(n/(2^i)) + 2^(i-1)

I'm not sure how to go from here (assuming what I have so far is correct)

Any help greatly appreciated and apologies for the crappy formatting

EDIT:

Using the master theory

a* T(n/b) + c(n^k)

I arrive at:

T(n) = n ^ (log2) [log base is 2]

O(n)

I'm not sure if this is the correct answer, still looking for help thank you!

Answer 1

Assuming that you don't know the answer, you can argue like this:

$T(n) = 2T(n/2) + 1 $.

Let $n = 2^m$ to get $T(2^m) = 2T(2^m/2)+ 1 = 2T(2^{m-1})+ 1 $.

Let $T(2^m) = U(m) $. $U(0) = T(2^0) = 1 $. Then $U(m) = 2U(m-1)+1 $. The values of $U$ are $1, 3, 7, 15, ...$

Looks like $U(m) =2^{m+1}-1 $.

(See below if not sure how to get this.)

If true for $m-1$, then

$\begin{array}\\ U(m) &=2U(m-1)+1\\ &=2(2^{m}-1)+1\\ &=2^{m+1}-2+1\\ &=2^{m+1}-1\\ \end{array} $

which completes the proof by induction.

Therefore $T(2^m) = U(m) =2^{m+1}-1 =2\cdot 2^m-1 $

so $T(n) = 2n-1 $ for $n$ a power of 2.

---

If $U(m) = 2U(m-1)+1 $, divide by $2^m$ to get $\dfrac{U(m)}{2^m} = \dfrac{2U(m-1)+1}{2^m} = \dfrac{U(m-1)}{2^{m-1}}+\dfrac{1}{2^m} $.

Let $V(m) = \dfrac{U(m)}{2^m} $, so that $V(m) = V(m-1)+\dfrac{1}{2^m} $ or $V(m) - V(m-1) =\dfrac{1}{2^m} $.

This telescopes, and we get

$\begin{array}\\ V(n)-V(0) &\sum_{m=1}^n (V(m) - V(m-1))\\ &\sum_{m=1}^n \dfrac{1}{2^m}\\ &=1-\dfrac1{2^n}\\ \end{array} $

so

$\dfrac{U(m)}{2^m}-\dfrac{U(0)}{2^0} =V(m)-V(0) =1-\dfrac1{2^m} $ or

$\begin{array}\\ U(m) &=2^m(U(0)+1-\dfrac1{2^m})\\ &=2^m(1+1-\dfrac1{2^m})\\ &=2^{m+1}-1\\ \end{array} $

Answer 2

The line under Or is incorrect in that the constant should be $2^i-1$, not $2^{i-1}$. You have essentially proposed that for $n=2^i$ you have $T(n)=2^i+2^i-1=2n-1$. You should now prove that by induction. Assume that $T(2^k)=2^{k+1}-1$ and show that $T(2^{k+1})=2^{k+2}-1$ by using the definition you are given.

Note that like many of these problems the definition of $T(n)$ only tells us what it is for $n$ a power of $2$. If you try to compute $T(3)$ you get stuck because you don't know $T(\frac 32)$. The setter really should say they only care about powers of $2$ or tell you how to handle the fractions.