O(N) vs O(NlogN)

Question

I came accros this example while working on Big-O notation

x=n
while(x>0)
{
    y=x
    while(y>0)
    {   
        y=y-1
    }
    x = x/2
}

Could, you explain me why it seems to have a O(N) complexity ?

This is new for me but I would expect it to be N LogN.

What am I missing ?

Thanks,

EDIT: this piece of code comes from here https://www.quora.com/How-can-we-check-for-the-complexity-log-n-and-n-log-n-for-an-algorithm?encoded_access_token=1b7e0a4d10f84d50b5fea810f5a89cea

The Quora page you linked does not say that code is `O(n)`. It says: "The above is O(n log n)" — , Oct 25 '18 at 15:45
@Amy he's right. You're reading the wrong "above" (example 8). — Amessihel, Oct 25 '18 at 15:48
In my opinion it should be O(n log n). I guess the author on mentioned site simply did a mistake... Just contact him to clear things up ;-) — Markus Safar, Oct 25 '18 at 15:50
*but I would expect it to be N LogN?* Why do you expect that? — jrook, Oct 25 '18 at 16:05
Please don't just ask us to solve the problem for you. Show us how you tried to solve the problem yourself, then show us exactly what the result was, and tell us why you feel it didn't work. See ["What Have You Tried?"](https://mattgemmell.com/what-have-you-tried/) for an excellent article that you really need to read. — jrook, Oct 25 '18 at 16:07
I did not ask you to solve this problem. My issue here is that I just don't get why in this case we end up ignoring the fact that the main loop is executed logN times — user10558547, Oct 25 '18 at 16:26

score 2 · Answer 1 · answered Oct 25 '18 at 16:04

Well, let's look how often the inner loop's body is executed:

x =   n:      n
x = n /  2: n /  2
x = n /  4: n /  4
x = n /  8: n /  8
x = n / 16: n / 16
x = n / 32: n / 32
x = n / 64: n / 64
until x < 1

Or put it together:

n + n / 2 + n / 4 + n / 8 + n / 16 + n / 32 + n / 64 ...

Which is easily seen is the same as:

n + n - n / 64

Now we want an upper bound, so we may ignore the last term. And for big-oh, the constant is also insignificant. So:

O(n)

score 2 · Answer 2 · answered Oct 25 '18 at 16:05

If you find how many times the inner loop runs, you find the complexity of the code. The inner loop runs n + n/2 + n/4 + ... n/k (where n/k>0) times. The maximum value of n/2 + n/4 + ... + n/k part is n-1. Thus, the code can not run more than 2n-1 times making the upper bound 2n-1 which is O(n)

O(N) vs O(NlogN)

2 Answers2