CODEWITHSUNDEEP
pythonalgorithmmathrecursionbig-o
Steven
Steven

Reputation: 195

Big-O notation for two simple recursive functions

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)

Upvotes: 8

Views: 4998

Answers (2)

siddstuff
siddstuff

Reputation: 1255

Finding cost using a recursion tree (through a visualize diagram).

recurrence relation of the function cost(n)

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

enter image description here

If at kth level input size become 0 (base condition where func terminates)
                                           n-k =0
                                              k=n


Total cost of the function (adding cost of each level) :
             T(n) = 2^0*c+ 2^1*c + 2^2*c + 2^3*c +.. .. . .+ 2^n * c
                  = O(2^n)

similar way we can find the time complexity of second function.

Upvotes: 7

templatetypedef
templatetypedef

Reputation: 373482

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 21 - 1, 22 - 1, 23 - 1, etc. More generally, we can prove that

T(n) = 2n+1 - 1

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

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

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

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!

Upvotes: 15

Related Questions