[SOLVED] How the complexity of the following code is O(nlogn)? – Stack Overflow

Issue

This Content is from Stack Overflow. Question asked by Sunil kumar

{
for(j=1;j<=i;j++)
{
}
}

How the complexity of the following code is O(nlogn) ?



Solution

Time complexity in terms of what? If you want to know how many inner loop operations the algorithm performs, it is not O(n log n). If you want to take into account also the arithmetic operations, then see further below. If you literally are to plug in that code into a programming language, chances are the compiler will notice that your code does nothing and optimise the loop away, resulting in constant O(1) time complexity. But only based on what you’ve given us, I would interpret it as time complexity in terms of whatever might be inside the inner loop, not counting arithmetic operations of the loops themselves. If so:

Consider an iteration of your inner loop a constant-time operation, then we just need to count how many iterations the inner loop will make.

You will find that it will make

1 + 2 + 4 + 8 + … + n

iterations, if n is a square number. If it is not square, it will stop a bit sooner, but this will be our upper limit.

We can write this more generally as

the sum of 2i where i ranges from 0 to log2n.

Now, if you do the math, e.g. using the formula for geometric sums, you will find that this sum equals

2n – 1.

So we have a time complexity of O(2n – 1) = O(n), if we don’t take the arithmetic operations of the loops into account.

If you wish to verify this experimentally, the best way is to write code that counts how many times the inner loop runs. In javascript, you could write it like this:

function f(n) {
    let c = 0;
    for(i=1;i<=n;i=i*2) {
      for(j=1;j<=i;j++) {
          ++c;
      }
    }
    console.log(c);
}

f(2);
f(4);
f(32);
f(1024);
f(1 << 20);

If you do want to take the arithmetic operations into account, then it depends a bit on your assumptions but you can indeed get some logarithmic coefficients to account for. It depends on how you formulate the question and how you define an operation.


This Question was asked in StackOverflow by Sunil kumar and Answered by Berthur It is licensed under the terms of CC BY-SA 2.5. - CC BY-SA 3.0. - CC BY-SA 4.0.

people found this article helpful. What about you?