Big-O designation for two simple recursive functions

Question

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

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 them use recursive relationships to solve this! The first execution time of a function can be described recursively as

T (0) = 1

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

That is, the base case requires a single completion, and otherwise we make two recursive calls for smaller instances of the problem and perform some configuration and cleaning operations. Decomposing some members of this repetition, we obtain

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

This series 1, 3, 7, 15, ... may look familiar, as 2 ¹ - 1, 2 ² - 1, 2 ³ - 1, etc. In the general case, we can prove that

T (n) = 2 ^{n + 1} - 1

We can do this by induction. As our basic case, T (0) = 1 = 2 ¹ - 1, so the statement is valid for n = 0. Now suppose that for some n T (n) = 2 ^{n +1} - 1. Then we have that

T (n + 1) = 2T (n) + 1 = 2 (2 ^{n + 1} - 1) + 1 = 2 ^{n + 2} - 2 + 1 = 2 ^{n + 2} - 1

And you're done! Since this recurrence works up to 2 ^{n + 1} - 1 = 2 (2 ⁿ ) - 1, we have that the execution time is & Theta; (2 ⁿ ).

The second functional runtime can be described recursively as

T (0) = 1

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

Deployment of 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, ..., therefore, as a rule, we can assume that

T (n) = n + 1

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

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

And you're done! Since the runtime is n + 1, the runtime is & Theta; (n).

Hope this helps!

Answer 2

Search for value using the recursion tree (through the visualization diagram).

recursive ratio of the cost of the function (n)

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

 If at kth level input size become 0 (base condition where func terminates) nk =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) 

Similarly, we can find the time complexity of the second function.