Geek asks and answers

Computational code snippet complexity

I have a program and am trying to calculate its complexity. I want to be sure that I’m 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 the third cycle is O (n), then together with the second cycle the complexity becomes O (n.log 4i), and the complexity of the entire program is O (p. (enter <sub> 4sub> i) 2 ). Am I right in my answer? Thanks

+5
source share
2 answers

The complexity of the inner inner loop is O (n). The average complexity is O (i / 4), which in turn is O (i). The complexity of the outermost loop is O (log 4n). There for a total of O code (nilog 4 n), which is equal to O (n. (Log 4n) 2 ).

+2

:

enter image description here

:

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 ++;
        }
    }
}

:

enter image description here

enter image description here

enter image description here

enter image description here

, .

, O (n)... , O (n²).

0

More articles:


All Articles