Hacker News Reader

Comment by bogomipz | Hacker News Reader

>"My rule of thumb here is that if I have to use a loop within a loop, that’s O(n^2)."

This might potentially do someone a disservice. The whole point of analysis is just that - to "analyze" the runtime and not resort to "rules of thumb."

The presence of nested for loops itself is not a good reason to declare something quadratic. Consider the following which is most certainly not O(N^2):

for (int i = 0; i < 1000; i++)

  for (int j = n; j >= 1; j = j / 2)

    // do something

EDIT: initialized j to the val of n on the inner loop per the comments below.

View on HN

For those who missed it, the absence of "n" in these loops makes "do something" happen a constant number of times. So as written by the OP the loops are currently O(1)

if for (int i = 0; i < 1000; i++) were instead

for (int i = 0; i < n; i++) - You'd have O(n)

If also for (int j = 1000; j >= 1; j = j / 2) were instead

for (int j = n; j >= 1; j = j / 2) - Then you'd have O(n log n)

OR for (int j = n; j >= 1; j -= 1) - O(n^2)

OR for (int j = n * 1000; j >= 1; j -= 1) - this is STILL O(n^2)

Well, as written, it is 'O(1)'. Or did you mean to put N instead of 1000?

The inner loop is log(N), it halves the value of J after every iteration. The "do something" was meant to stand for a constant time operation so that it's N log N. But my point was really that if you told an interviewer that it was O(N^2) simply because it contained nested for loops it would be a very clear sign that you didn't fully grasp Big O.

Yes, but my point is that, as written, there is no dependency on N. Thus, O(1).

It's a subtle point, but anon946 was pointing out that since your loops are fixed at 1000, this entire thing is O(1) (granted, with a large constant). You should change all of the "1000" to "n". That would make it O(n lg n).

edit: you've now edited the inner loop to be n, but the outer loop is still 1000. This is still wrong, as the entire algorithm is now just O(lg n).

Nah, every algorithm that is O(N logN) is also O(n^2). That would be a sign, that you as an interviewer didn't fully grasp Big O.

OP here - O(N log N) is not O(n^2). If n is 1000 then log n is 10, which is 1000 * 10 which is 10,000. That's a bit less than 1000 * 1000.

You're wrong. n lg n grows asymptotically slower than n^2, and is thus is O(n^2). n is also O(n^2), as is 1, or even sin(n). All of this follows directly from the definition [0].

Also the fact that you're plugging numbers in for n indicates to me that you don't actually understand big O notation, which is surprising since the original article is decent.

[0] https://en.wikipedia.org/wiki/Big_O_notation#Formal_definiti...

Nah "f(n) is said to be in O( g(n) )" formally speaking but practically speaking an algorithm in some production code that runs in O(n log n) vs one that runs in O(n^2) are not the same thing at all.

That would be a sign that you as a candidate are being needlessly pedantic and usually a red flag.

You're confusing O with Theta.

No I am most certainly not. Nowhere did anything I said in the comment above indicated I was referring to both a lower AND upper bound which is Big Theta.

Honestly it sounds as if you might not understand the difference between Theta and O. I understand that a function that is O(N^2) grows no faster than O(N^3) asymptotically speaking however the intention of my original comment and example is quite clear about their context.

Please stop, you are adding nothing to the discussion.

You most certainly are confusing O with Theta. O is just an asymptotic upper bound. Of course a function that’s bounded by n lg n is also bounded by n^2.

No I am not. The other commenter inexplicably and needlessly decided to introduce Theta and assert that I was confused.

Maybe you might reread my original comment. This whole side discussion is of no value to my original comment which has a very clear and very narrow context.

I am not sure why the both of you want to belabor some ancillary talking point that you yourselves decided to introduce. It is of exactly no value to the context of my original comment and not in the least bit productive.

OP here. Agree that thinking about code is better than using a rule of thumb, but we need to start somewhere don't we? I tried to make it clear in the post that looping over n items within an n loop is n * n.

Big-O is an upper bound. Something that's O(n) is also O(n^2).

Reply on news.ycombinator.com