4 ms·

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.

by enedil 8y ago

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.

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.

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