Big-O notation for two simple recursive functions

Question

I have two recursive functions in Python and simply just want to know the Big O Notation for them. What is the Big O for each these?

def cost(n):
    if n == 0:
        return 1
    else:
        return cost(n-1) + cost(n-1)

def cost(n):
    if n == 0:
        return 1
    else:
        return 2*cost(n-1)

Answer 1

Let's use recurrence relations to solve this! The first function's runtime can be described recursively as

T(0) = 1

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

That is, the base case takes one time unit to complete, and otherwise we make two recursive calls to smaller instances of the problem and do some amount of setup and cleanup work. Expanding out some terms in this recurrence, we get

• T(0) = 1
• T(1) = 2T(0) + 1 = 2 + 1 = 3
• T(2) = 2T(1) + 1 = 2 × 3 + 1 = 7
• T(3) = 2T(2) + 1 = 2 × 7 + 1 = 15

This series 1, 3, 7, 15, ... might look familiar, since it's 2¹ - 1, 2² - 1, 2³ - 1, etc. More generally, we can prove that

T(n) = 2ⁿ⁺¹ - 1

We can do this by induction. As our base case, T(0) = 1 = 2¹ - 1, so the claim holds for n = 0. Now assume that for some n that T(n) = 2ⁿ⁺¹ - 1. Then we have that

T(n + 1) = 2T(n) + 1 = 2(2ⁿ⁺¹ - 1) + 1 = 2ⁿ⁺² - 2 + 1 = 2ⁿ⁺² - 1

And we're done! Since this recurrence works out to 2ⁿ⁺¹ - 1 = 2(2ⁿ) - 1, we have that the runtime is Θ(2ⁿ).

The second function's runtime can be described recursively as

T(0) = 1

T(n + 1) = T(n) + 1

Expanding out some terms:

• T(0) = 1
• T(1) = T(0) + 1 = 1 + 1 = 2
• T(2) = T(1) + 1 = 2 + 1 = 3
• T(3) = T(2) + 1 = 3 + 1 = 4

This gives 1, 2, 3, 4, ..., so more generally we might guess that

T(n) = n + 1

We can prove this inductively again. As a base case, if n = 0, then T(0) = 1 = 0 + 1. For the inductive step, assume that for some n that T(n) = n + 1. Then

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

And we're done! Since the runtime is n + 1, the runtime is Θ(n).

Hope this helps!