Big(O) time complexity unable to find-CodePudding

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)?

CodePudding user response：

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).

CodePudding user response：

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)

CodePudding user response：

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)

CodePudding user response：

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.