5 ms·

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

bogomipz 8y ago
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.
- anon946 8y ago
  Yes, but my point is that, as written, there is no dependency on N. Thus, O(1).
- vecter 8y ago
  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).
- enedil 8y ago
  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.
  - robconery 8y ago
    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.
    - vecter 8y ago
      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_definition https://en.wikipedia.org/wiki/Big_O_notation#Formal_definiti...
  - bogomipz 8y ago
    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.
    - enedil 8y ago
      You're confusing O with Theta.
      - bogomipz 8y ago
        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.
        vecter 8y ago
        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.
        bogomipz 8y ago
        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.

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.

anon946 8y ago
Yes, but my point is that, as written, there is no dependency on N. Thus, O(1).
vecter 8y ago
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).
enedil 8y ago
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.
- robconery 8y ago
  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.
  - vecter 8y ago
    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_definition https://en.wikipedia.org/wiki/Big_O_notation#Formal_definiti...
- bogomipz 8y ago
  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.
  - enedil 8y ago
    You're confusing O with Theta.
    - bogomipz 8y ago
      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.
      - vecter 8y ago
        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.
        bogomipz 8y ago
        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.