5 ms·

>"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 analy

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

anon946 8y ago
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.
gridspy 8y ago
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)
robconery 8y ago
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.
Grue3 8y ago
Big-O is an upper bound. Something that's O(n) is also O(n^2).

anon946 8y ago

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.

gridspy 8y ago

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)

robconery 8y ago

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.

Grue3 8y ago

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