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

Question

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)?

Yea that seems like O(n^2). Inner-loop runs n-times, recursion happens n-times. — Matthew E. Miller, Aug 20 '19 at 16:07
Possible duplicate of [Big O, how do you calculate/approximate it?](https://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it) — Prune, Aug 20 '19 at 16:45

Renat · Answer 1 · 2019-08-20T16:19:49.283

2

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)

edited Aug 20 '19 at 16:19

answered Aug 20 '19 at 16:09

Renat

score 0 · Answer 2 · answered Aug 21 '19 at 02:54

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)

2 Answers2