5 ms·

O() doesn't necessarily describe worst-case behaviour. It just provides an asymptotic upper bound. So a quadratic sorting algorithm can still be said to be O(n^

by tromp 1y ago

O() doesn't necessarily describe worst-case behaviour. It just provides an asymptotic upper bound. So a quadratic sorting algorithm can still be said to be O(n^3), although that might be a little misleading.

samwho 1y ago
I'd love to hear more about how a quadratic sorting algorithm could be said to be O(n^3). That isn't intuitive to me.
- ndriscoll 1y ago
  Because |n^2|≤|n^3| as n→∞, so if |f| ≤ A|n^2| as n→∞, then |f| ≤ A|n^3| as n→∞.
- mfsch 1y ago
  Technically the big O notation denotes an upper bound, i.e. it doesn’t mean “grows as fast as” but “grows at most as fast as”. This means that any algorithm that’s O(n²) is also O(n³) and O(n⁴) etc., but we usually try to give the smallest power since that’s the most useful information. The letter used for “grows as fast as” is big Theta: https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
  - samwho 1y ago
    Ahh I see, thank you!
didibus 1y ago
In math that’s true, but a practitioner software engineer uses it to mean the common "tightest" upper bound we can easily prove for the case we care about (worst, amortized, average, etc.), and not the actual tightest possible bound.
- monkeyelite 1y ago
  It has a meaning already - and that is the sets of function which satisfy the condition. So O(n^2) is a subset of O(n^3)
  - arethuza 1y ago
    Any everything is O(BB(n))
  - didibus 1y ago
    > It has a meaning already Natural language tends to work like that, many words take on different meaning in different context, and the dictionary often needs to add alternate definitions as language evolves. If you come to a software engineering interview and take the mathematical meaning and answer O(n^3), you won't get the job. You need to know the linga franca of the trade, not just the textbooks. I know this can be frustrating, I just wouldn't really recommend staking your ground on this mountain. The other mistake, is to assume the interviewer doesn't know better, and you do, and try to explain their mistake. A lot of them know very well, you simply didn't understand correctly the ask because you got confused with the context of the problem statement, and it shows you didn't adapt to the working environment successfully. And if you think that's bad, wait till you talk to product ;)
    - monkeyelite 1y ago
      You’re describing a situation of poor communication - not a fault for using the precise definition of Big oh.
      - didibus 1y ago
        You know the correct definition of BigO, which is great. Where things fell short was recognizing how industry jargon often stretches textbook terms. The skill is being able to adapt, realize when people are talking about a related but different concept, and engage on that level. The strongest candidates handle both the theory and the communication. So I'd ding the candidate for poor communication.

by tromp 1y ago

samwho 1y ago

I'd love to hear more about how a quadratic sorting algorithm could be said to be O(n^3). That isn't intuitive to me.

ndriscoll 1y ago
Because |n^2|≤|n^3| as n→∞, so if |f| ≤ A|n^2| as n→∞, then |f| ≤ A|n^3| as n→∞.
mfsch 1y ago
Technically the big O notation denotes an upper bound, i.e. it doesn’t mean “grows as fast as” but “grows at most as fast as”. This means that any algorithm that’s O(n²) is also O(n³) and O(n⁴) etc., but we usually try to give the smallest power since that’s the most useful information. The letter used for “grows as fast as” is big Theta: https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer_science https://en.wikipedia.org/wiki/Big_O_notation#Use_in_computer...
- samwho 1y ago
  Ahh I see, thank you!

didibus 1y ago

In math that’s true, but a practitioner software engineer uses it to mean the common "tightest" upper bound we can easily prove for the case we care about (worst, amortized, average, etc.), and not the actual tightest possible bound.

monkeyelite 1y ago
It has a meaning already - and that is the sets of function which satisfy the condition. So O(n^2) is a subset of O(n^3)
- arethuza 1y ago
  Any everything is O(BB(n))
- didibus 1y ago
  > It has a meaning already Natural language tends to work like that, many words take on different meaning in different context, and the dictionary often needs to add alternate definitions as language evolves. If you come to a software engineering interview and take the mathematical meaning and answer O(n^3), you won't get the job. You need to know the linga franca of the trade, not just the textbooks. I know this can be frustrating, I just wouldn't really recommend staking your ground on this mountain. The other mistake, is to assume the interviewer doesn't know better, and you do, and try to explain their mistake. A lot of them know very well, you simply didn't understand correctly the ask because you got confused with the context of the problem statement, and it shows you didn't adapt to the working environment successfully. And if you think that's bad, wait till you talk to product ;)
  - monkeyelite 1y ago
    You’re describing a situation of poor communication - not a fault for using the precise definition of Big oh.
    - didibus 1y ago
      You know the correct definition of BigO, which is great. Where things fell short was recognizing how industry jargon often stretches textbook terms. The skill is being able to adapt, realize when people are talking about a related but different concept, and engage on that level. The strongest candidates handle both the theory and the communication. So I'd ding the candidate for poor communication.