CODEWITHSUNDEEP
c++algorithmruntimebig-otime-complexity
argamanza
argamanza

Reputation: 1142

Trying to calculate running time of an algorithm

I have the following algorithm:

for(int i = n; i > 0; i--){
    for(int j = 1; j < n; j *= 2){
        for(int k = 0; k < j; k++){
            ... // constant number C of operations
        }
    }
}

I need to calculate the algorithm's running time complexity,

I'm pretty sure the outer loop runs O(n) times, the middle loop runs O(log(n)) times, and the inner loop runs O(log(n)) times as well, but I'm not so sure about it.

The final result of the running time complexity is O(n^2), but I have no idea how.

Hope someone could give me a short explanation about it, thanks!

Upvotes: 3

Views: 710

Answers (1)

nullptr
nullptr

Reputation: 11058

For each i, the second loop runs j through the powers of 2 until it exceeds n: 1, 2, 4, 8, ... , 2h, where h=int(log2n). So the body of the inner-most loop runs 20 + 21 + ... + 2h = 2h+1-1 times. And 2h+1-1 = 2int(log2n)+1-1 which is O(n).

Now, the outer loop executes n times. This gives complexity of the whole thing O(n*n).

Upvotes: 5

Related Questions