Big(O) time complexity unable to find

Question

What is time complexity of following code :

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

**

is it O(n) or O(log(n)*n)?

**

Answer 1

I think this type of question has already been answered in past posts. I'll cover the basic premise for this one. Suppose N = 8

First Loop (i)    No. Of Second Loop Runs 
8                 8
8/2               8/2
8/4               8/4
8/8               8/8

Generalizing & adding up no. of times second loop will run for above process:

N + (N / 2) + (N / 4) + ... + 1

We need to solve the above series to get overall time complexity. Let's take a case where this series is infinite (very large). In that case the formula for this kind of summation is

a + (a / r) + ... = a / (1 - r), where a is first term and r is common ratio

So, result will be:

N + (N / 2) + (N / 4) + ... = N / (1 - (1/2)) = (2 * N)

This is the maximum (upper-bound) of the series sum. 2 is a constant term . So we can conclude time complexity for worst case will be O(N).

Answer 2

Inner loop executes i-1 times. Initialy i=n, and each iteration i=n/(2^k). So at the first, inner loop runs n times. Next iteration, inner loop runs n/2 times, and in the last iteration inner loop runs one time. So you can write as a serie:

Let T(n) be time complexity of your code, then

T(n)=n+ n/2 + n/4 + ... + 1=O(n)

Answer 3

The outer loop run a total of log(n) times. Look at inner loop. First time, the inner loop run n times, second time run n/2 times and so on, so it makes below series

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

Sum of this is equal to 2*n, and this means it's O(n)

Thus, since outer loop runs O(logn) times and inner loop runs O(n) times, the time complexity is O(n).

Since the inner loop doesn't take n steps, it isn't O(nlogn).

Indeed the sum of all steps taken is O(n)

Answer 4

All the answers here are useful. I am writing this one to just discuss some basic things. I am assuming you don't have clear idea about one or more from this list and that is what making you confused about this problem.

Now in all of the answers they are taking into account, the innermost expression? You should ask yourself "why?" Since that would make you solve these problems next time. The idea is, the amount of time a program takes to run or finish is dependent on hardware and many other stuff. Long story short, it won't be comparable if you use execution time as is. Maybe your machine is faster than mine etc etc.

That's why we start to identify the elementary operations that the algorithm does repeatedly. Now how to identify these elementary operations. Usually these are the ones which are executed most frequently and irrespective of when they are executed time to perform this operation is constant. The innermost expression is executed most frequently. So that's why they are considering it.

You might ask, there are for loop comparisons which are also behaving like that (the second for loop operation especially). Should we consider it as a elementary operation? The answer is "yes" but it won't change anything. It would just add a constant offset to the innermost expression making the final complexity same. By simply considering only the innermost expression as unit time elementary operation, you are taking into account the most important thing. Note it's not as per unit of time - it's just that we are counting how many times it is executed.

After this the analysis becomes easier. You have to tell me, for a length n array how many times the innermost expression is executed. And that's what is being done over here in other answers. Hope it clarifies few things.

Answer 5

Just to validate Rahul's derivation, you can run the following script (in C#) to see that the count is incremented just under 2N times for any value of N that you provide.

int[] ns = { 10, 100, 1000, 10000, 100000 };

foreach (int N in ns)
{
    int count = 0;
    for (int i = N; i > 0; i /= 2)
    {
        for (int j = 0; j < i; j++)
        {
            count += 1;
        }
    }

    Console.WriteLine("N: " + N);
    Console.WriteLine("count: " + count);
}

Testing with a few small values of N is a good way to estimate how an algorithm will scale when you're stuck in trying to figure out the Big-O complexity mathematically, or just to prove that your derivation is correct.

Answer 6

In the first iteration i=N, and so the number of different values assigned to j is N. In the second iteration i=N/2, in the third iteration i=N/4, and so on. Therefore, total cost of the program is on the order of N + N/2 + N/4 + ... , which is at most 2N. Hence, the time complexity of the algorithm is O(N). Note that the number of terms in the sum is the number of different values assigned to i, which is about log N. But these terms decrease at a geometric rate, and so the total cost of the sum is dominated by the first term. It would not be incorrect to say that there are log N terms in the sum, and each term is at most N, and therefore the total cost is O(N log N). It's just that this analysis is crude and the resulting upper bound O(N log N) is not tight.