CODEWITHSUNDEEP
algorithmfor-loopbig-otime-complexityasymptotic-complexity
user2110714
user2110714

Reputation:

Computational complexity of a piece of code

I have got a program, and trying to compute its complexity. I want to be sure i am not mistaken

for(int i=4; i<=n; i=i*4)
{
    cout<<"counter for first loop: "<<++count1<<endl;
    for(int j=i;j>=0;j=j-4)
    {
        cout<<"counter for second loop: "<<++count2<<endl;
        for(int k=0;k<=n;k++)
        {
            cout<<"counter for third loop: "<<++count3<<endl;
        }
    }
}

Here, the complexity of third loop is O(n), then together with the second loop, the complexity becomes O(n.log4i), and the complexity of whole program is O(n.(log4i)2). Am i right in my answer? Thanks

Upvotes: 5

Views: 242

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

You can proceed formally like the following:

enter image description here

Executing this fragment:

sum = 0;
for( i = 4 ;  i <= n;  i = i * 4 ) {
    for( j = i ; j >= 0 ; j = j - 4 ) {
        for( k = 0 ; k <= n ; k ++ ) {
            sum ++;
        }
    }
}

We obtain:

enter image description here

enter image description here

enter image description here

enter image description here

Results exactly compatible with the formula above.

Besides, both inner loops' runtime is O(n) ... which means that, when executed together, we get O(n²).

Upvotes: 0

Deepu
Deepu

Reputation: 7610

The complexity of the inner most loop is O(n). The complexity of the middle one is O(i/4), which in turn is O(i). The complexity of the outer most loop is O(log4n). There for the total complexity of the code is O(n.i.log4n) which is equal to O (n.(log4n)2).

Upvotes: 2

Related Questions