CODEWITHSUNDEEP
c++algorithmrecursionbig-o
LP_CS
LP_CS

Reputation: 49

Big-O complexity of this algorithm

CODE:

void fun(int n){
    if(n>2){
        for(int i=0;i<n;i++){
            j=0;
            while(j<n){
                cout<<j;
                j++;
            }
        }
        fun(n/2);
    }
}

Here's what I think: The recursive part is running log(n) times ? and during each recursive call, the for loop will run n^2 times, with n changing to half in each recursive call. So is it n^2 + (n^2)/4 + (n^2)/16 + ... + 1?

Upvotes: 2

Views: 104

Answers (3)

user1196549
user1196549

Reputation:

The number of writes to cout is given by the following recurrence:

T(N) = N² + T(N/2).

By educated guess, T(N) can be a quadratic polynomial. Hence

T(N) = aN²+bN+c = N² + T(N/2) = N² + aN²/4+bN/2+c.

By identification, we have

3a/4 = 1
b/2 = 0
c = c.

and 

T(N) = 4N²/3 + c.

With T(2)= 0,

T(N) = 4(N²-4)/3

which is obviously O(N²).

Upvotes: 2

Serge Ballesta
Serge Ballesta

Reputation: 148910

This is simple mathematics. The complexity is n^2 + (n^2)/4 + (n^2)/16 + ... + 1. It is (n² * (1 + 1/4+ ...)) . And the maths says that the infinite serie converges to 4/3 (the formula is: 1 / (1 - 1/4)).

It gives actually O(n2).

Upvotes: 0

hangc
hangc

Reputation: 5473

You are right, so the big(O) is n^2 since the sum of the series n^2 + (n^2)/4 + (n^2)/16 + ... + 1 never exceeds 2n^2

Upvotes: 3

Related Questions