CODEWITHSUNDEEP
data-structurestime-complexitynested-loops
Ankita
Ankita

Reputation: 37

time-complexity of nested loop

Why is the time-complexity of

function (n)
{
    //this loop executes n times

    for( i = 1 ; i <= n ; i + + )
    //this loop executes j times with j increase by the rate of i
    for( j = 1 ; j <= n ; j+ = i )
    print( “*” ) ;

}

Its running time is n*(n^1/2)=n^3/2

so, O(n^3/2)

Please explain with mathematical steps.

Thank you in advance.

Upvotes: 1

Views: 281

Answers (1)

blazs
blazs

Reputation: 4845

The running time is bounded by O(n^{3/2}), but that's not tight!

Notice that the inner loop makes O(n/i) iterations for each i=1,2,...n), thus the time complexity is O(n * (1 + 1/2 + 1/3 + ... + 1/n)) = O(n log n).

This is because 1+1/2+1/3+...+1/n=O(log n) as it is the well-known harmonic series.

Upvotes: 1

Related Questions