Search code examples
calgorithmcomplexity-theory

What is the time complexity of this little code?

What is the time complexity of this little code?

int count = 0;
for (int i = n; i > 0; i = i/2) {
    for (int j = 0; j < i; j++) {
        count++;
    }
}

I want to know the time complexity of this code. To me I calculated as O(n log n) because outer loop runs logn times and inner loop runs O(n) times. But i am confused because the inner loop j depends on i. So what will be the actual time complexity and why?

Solution

  • The exact sum is

    n + n/2 + n/4 + ... + 1

    which is

    n * (1 + 1/2 + 1/4 + ... + 1/n)

    The sum of the non-negative powers of 1/2 is well known to approach 2 in the limit, so the total sum approaches 2*n. As a result, the complexity is O(n); i decreases quickly enough to avoid the linarithmic growth.