CODEWITHSUNDEEP
algorithmmathcomplexity-theorybig-o
Chin
Chin

Reputation: 20725

What is the running time complexity of this algorithm

What is the time complexity of this algorithm:

sum = 0
i = 1

while (i < n) {

    for j = 1 to i {
        sum = sum + 1
    }

    i = i*2;
}

return sum

I know that the while loop is O(logn), but what is the complexity of the for loop? Is it O(n) or O(logn)?

Upvotes: 1

Views: 874

Answers (1)

templatetypedef
templatetypedef

Reputation: 373462

One way to analyze this would be to count up the number of iterations of the inner loop. On the first iteration, the loop runs one time. On the second iteration, it runs two times. It runs four times on the third iteration, eight times on the fourth iteration, and more generally 2k times on the kth iteration. This means that the number of iterations of the inner loop is given by

1 + 2 + 4 + 8 + ... + 2r = 2r + 1 - 1

Where r is the number of times that the inner loop runs. As you noted, r is roughly log n, meaning that this summation works out to (approximately)

2log n + 1 - 1 = 2(2log n) - 1 = 2n - 1

Consequently, the total work done by the inner loop across all iterations in O(n). Since the program does a total of O(log n) work running the outer loop, the total runtime of this algorithm is O(n + log n) = O(n). Note that we don't multiply these terms together, since the O(log n) term is the total amount of work done purely in the maintenance of the outer loops and the O(n) term is total amount of work done purely by the inner loop.

Hope this helps!

Upvotes: 7

Related Questions