python - Big-O notation for two simple recursive functions -

i have 2 recursive functions in python , want know big o notation them. big o 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) 

let's use recurrence relations solve this! first function's runtime can described recursively as

t(0) = 1

t(n + 1) = 2t(n) + 1

that is, base case takes 1 time unit complete, , otherwise make 2 recursive calls smaller instances of problem , amount of setup , cleanup work. expanding out terms in recurrence, 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 familiar, since it's 2¹ - 1, 2² - 1, 2³ - 1, etc. more generally, can prove that

t(n) = 2ⁿ⁺¹ - 1

we can induction. our base case, t(0) = 1 = 2¹ - 1, claim holds n = 0. assume n t(n) = 2ⁿ⁺¹ - 1. have that

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

and we're done! since recurrence works out 2ⁿ⁺¹ - 1 = 2(2ⁿ) - 1, have runtime θ(2ⁿ).

the second function's runtime can described recursively as

t(0) = 1

t(n + 1) = t(n) + 1

expanding out 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, ..., more might guess that

t(n) = n + 1

we can prove inductively again. base case, if n = 0, t(0) = 1 = 0 + 1. inductive step, assume n t(n) = n + 1. then

t(n + 1) = t(n) + 1 = n + 1 + 1 = n + 2

and we're done! since runtime n + 1, runtime θ(n).

hope helps!