Search code examples
algorithmiterationtime-complexityrecurrenceupperbound

Recurrence relation: iteration solving

There is a recurrence relation as following:

T(n) = 2 T(n-1) + O(1) for n > 1 
otherwise, its T(n) = O(1)

By iteration , so far I got like,

T(n) = 2(2T(n-2) + 1) + 1 --- 1
T(n) = 2(2(2T(n-3) + 1) + 1) + 1 ---- 2
T(n) = 2(2(2(2T(n-4) + 1) + 1) + 1) + 1 ------3
T(n) = 2(2(2(2(2T(n-5) + 1) + 1) + 1) + 1) +1 ----- 4

I am not sure what to do next to find the upper bound time complexity. Could anyone please help me with this.

Solution

  • Look at step 4

    T(n) = 2(2(2(2(2T(n-5) + 1) + 1) + 1) + 1) +1 ----- 4
T(n) = 2(2(2(2(2T(n-5))))) + 16 + 8 + 4 + 2 +1 = 
T(n) = 2^4* 2T(n-5) + 2^4 + 2^3 + 2^2 + 2^1 + 2^0 =
T(n) = 2^4* 2T(n-5) + 2^5 -1 =

    Similarly, if you do the same and develop one more time you get:

    T(n) = 2^5 *2T(n-6) + 2^5 + 2^5-1
T(n) = 2^5 * 2T(n-6) + 2^6-1

    By now we can understand that if we develop it until base of T(1), we get:

    T(n) = .... = 2^(n) -1

    Note that this method is only giving intuition to solving the problem and IT IS NOT A PROOF.

    To formally prove the claim you can use induction, and claim the hypothesis T(n) = 2^n -1:

    Base: T(1) = 1 = 2^1 -1

    Induction Hypothesis: For all k<n, T(k) = 2^k-1

    Proof:

    T(n) = 2T(n-1) +1 =(i.h.) 2* (2^(n-1) -1) + 1 = 2^n -2 + 1 = 2^n - 1

    Remark: The T(1) base clause is actually C, and similarly T(n) = 2T(n-1)+C for some constant and not 1, but I use 1 for simplicity. The logic does not chagne at all when changing it to C.