CODEWITHSUNDEEP
algorithmrecursion
kevin
kevin

Reputation: 309

Time complexity of the recursive algorithm each recursion takes O(N)

I have a algorithm, the pseudo code below:

def foo(n):
    if n == 0
    return;

    // Loop below take O(N)
    for(i=0; i<n:i++){
   .... 
    }
    foo(n-1):

The idea is that each recursion takes n time, and there are n recursions.

The total time should be like 1 + 2 3 + 4 +5 + ... +n

Can it be proved as O(n*n)?

Upvotes: 0

Views: 57

Answers (2)

Daniel
Daniel

Reputation: 7724

First, you have n iterations in the for loop, then the function will repeat with n-1, n-2, ..., 0.

It's easy to see that n + (n-1) + (n-2) + ... + 1 = (n+1) * n/2 = (n^2 + n)/2 = O(n^2).

To evaluate Big O, that is, the complexity of the worst case, remember you have to ignore the all the coeficients, constants and lower power terms:

(n^2 + n)/2 = (1/2) * (n^2 + n)

O( (1/2) * (n^2 + n) ) = O(n^2 + n) = O(n^2)

Upvotes: 0

Renat
Renat

Reputation: 8962

Yes, it is O(n^2).

The sum of n natural numbers is: n * (n+1) / 2, link. Which is different to n^2 by a constant factor, so O(n * (n+1) / 2) == O(n^2)

Upvotes: 2

Related Questions