Deduct time complexity from this Recurrence formula?

Question

I was reading a time complexity calculation related question on SO but I can't comment there (not enough reps). What's the time complexity of this algorithm for Palindrome Partitioning?

I have a question regarding going from 1st to 2nd equation here:

Now you can write the same expression for H(n-1), then substitute back to simplify:

H(n) = 2 H(n-1) + O(n) =========> Eq.1

And this solves to

H(n) = O(n * 2^n) =========> Eq.2

Can someone illustrate how he got Eq.2 from Eq.1? Thank you.

Answer 1

They are wrong.

Let's assume that O refers to a tight bound and substitute O(n) with c * n for some constant c. Unrolling the recursion you will get:

When you finish to unroll recursion n = i and b = T(0).

Now finding the sum:

Summing up you will get:

So now it is clear that T(n) is O(2^n) without any n

---

For people who are still skeptical about the math:

• solution to F(n) = 2F(n-1) + n
• solution to F(n) = 2F(n-1) + 99n

Answer 2

We need to homogenize the equation, in this simple case just by adding a constant to each side. First, designate O(n) = K to avoid ealing with the O notation at this stage:

H(n) = 2 H(n-1) + K

Then add a K to each side:

H(n) + K = 2 (H(n-1) + K)

Let G(n) = H(n) + K, then

G(n) = 2 G(n-1)

This is a well-known homogeneous 1-st order recurrence, with the solution

G(n) = G(0)×2ⁿ = G(1)×2^n-1

Since H(1) = O(n), G(1) = H(1) + K = O(n) + O(n) = O(n),

G(n) = O(n)×2^n-1 = O(n×2^n-1) = O(n×2ⁿ)

and

H(n) = G(n) - K = O(n×2ⁿ) - O(n) = O(n×2ⁿ)

Answer 3

Eq 1. is a recurrence relation. See the link for a tutorial on how to solve these types of equations, but we can solve via expansion as below:

H(n) = 2H(n-1) + O(n)
H(n) = 2*2H(n-2) + 2O(n-1) + O(n)
H(n) = 2*2*2H(n-3) + 2*2O(n-2) + 2O(n-1) + O(n)
...
H(n) = 2^n*H(1) + 2^(n-1)*O(1) + ... + 2O(n-1) + O(n)

since H(1) = O(n) (see the original question)
H(n) = 2^n*O(n) + 2^(n-1)*O(1) + ... + 2O(n-1) + O(n)
H(n) = O(n * 2^n)