5 ms·

Every time I see an introduction to Big-O notation, I immediately go look for a section about the worst case to find the most common, fundamental misconception

Every time I see an introduction to Big-O notation, I immediately go look for a section about the worst case to find the most common, fundamental misconception that is present in nearly every such text. Lo and behold: > Because it's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement, big O notation always describes the worst-case scenario. This is not true. I'm on my phone, so I can't be bothered to explain this in more detail, but there is plenty of information about this online.

lordleft 1y ago
Are you referring to the fact that Big O has notation and concepts revolving around best-case/average case scenarios, as well as worst-case scenarios?
- School-Cotton 1y ago
  It is the same notation in either case. The worst-case runtime of quicksort is O(n^2). The average runtime is O(n * log(n)).
bonoboTP 1y ago
Yes. The notation can be used to describe how fast any function grows. That function may be a worst-case runtime wrt. input length, the average-case runtimve wrt. input length, or anything else, really. But the most common usage is indeed worst-case analysis, especially in intro courses. This is also wrong in the article: > You may sometimes see the Greek letter "theta", Θ, instead of the letter O in big O notation. This is used when the best and worst case have the same order of growth. We can't use it for bubble sort because the best case is O(n) and the worst case is O(n^2). It conflates two different, orthogonal concepts: upper vs lower bounds on the one hand, and best vs worst case analysis on the other. The phrase "the best case is O(n)" already contradicts "big O notation always describes the worst-case scenario". They clearly use it for best case right there in the article.
- samwho 1y ago
  I’d love to hear how those two things differ, and how I could include it in the post in a way that won’t be too scary for a beginner to the topic. That section in particular has already seen several revisions based on other peoples’ comments.
  - bonoboTP 1y ago
    Basically, for each input length, you can have different runtimes depending on the contents of that input. If you always pick the highest runtime for each length, that gives you a specific function. You can then derive either a lower or an upper bound for that function. Same for the best case. You can state four combinations in their common sense intuition as - even in the worst case, the runtime grows only at most as fast as n^2 (modulo multiplication and addition) - in the worst case, the runtime can grow at least as fast as n^2 - in the best case, the runtime can grow only at most as fast as n^2 - even in the best case, the runtime grows at least as fast as n^2 One can imagine it as not just a single curve on a function plot, but a band, a range. Then the top line of this range can be bounded from above or below, and the bottom can also be bounded from above or below. The common case is when you give a bound for the top curve, from above. How to work this into the article, I don't know, sorry.
    - samwho 1y ago
      I appreciate you taking the time to explain this to me, thank you. I feel like the way I have it is a reasonable, if strictly incorrect, simplification for someone new to the material. When I write these, I have the newly-hired bootcamp grad as my target audience. Someone who has been taught the basics for how to write code for the web and work as a junior within a company, but has no computer science background. I want them to understand enough to make sense of what they see.
      - bonoboTP 1y ago
        Maybe like this: "It's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement. In such cases we typically use big O notation to describe the worst-case scenario. However, note that we may perform similar analysis on the best case or the average case as well." But here: > You may sometimes see the Greek letter "theta", Θ, instead of the letter O in big O notation. This is used when the best and worst case have the same order of growth. We can't use it for bubble sort because the best case is O(n) and the worst case is O(n^2). This is plain false, the worst-case runtime of bubble sort is indeed Θ(n^2). Either delete it, or write about the upper bound / lower bound thing.
samwho 1y ago
It’s okay, you’re not the first to point it out to me! I’d be interested to hear how you would explain it when you’re at a more appropriate device.
- IceDane 1y ago
  TLDR: Different contexts, different analyses. You can do a best-case, average-case and worst-case analysis. A linear search is O(1) in the best case, for example. Maybe this comes across as nitpicky to some, but that doesn't make the text any less incorrect, unfortunately. It's an extremely common misconception, however, and I would say that a huge proportion of students that go through an introductory course on this subject come out thinking the same thing. > It’s okay, you’re not the first to point it out to me! It would be nice if you corrected it - there are already too many people making this mistake online.
  - samwho 1y ago
    So your contention is with the word “always”? It doesn’t always mean worst case? I got told off by someone else for _not_ saying this. I really just want to find the way of describing this that won’t net me comments like yours. It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best.
    - jibal 1y ago
      > I got told off by someone else for _not_ saying this. And what made you think they were right? > I really just want to find the way of describing this that won’t net me comments like yours. Do research. There's a large literature on algorithmic complexity ... maybe start with https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best. non sequitur
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)

lordleft 1y ago

Are you referring to the fact that Big O has notation and concepts revolving around best-case/average case scenarios, as well as worst-case scenarios?

School-Cotton 1y ago
It is the same notation in either case. The worst-case runtime of quicksort is O(n^2). The average runtime is O(n * log(n)).

bonoboTP 1y ago

Yes. The notation can be used to describe how fast any function grows. That function may be a worst-case runtime wrt. input length, the average-case runtimve wrt. input length, or anything else, really. But the most common usage is indeed worst-case analysis, especially in intro courses. This is also wrong in the article: > You may sometimes see the Greek letter "theta", Θ, instead of the letter O in big O notation. This is used when the best and worst case have the same order of growth. We can't use it for bubble sort because the best case is O(n) and the worst case is O(n^2). It conflates two different, orthogonal concepts: upper vs lower bounds on the one hand, and best vs worst case analysis on the other. The phrase "the best case is O(n)" already contradicts "big O notation always describes the worst-case scenario". They clearly use it for best case right there in the article.

samwho 1y ago
I’d love to hear how those two things differ, and how I could include it in the post in a way that won’t be too scary for a beginner to the topic. That section in particular has already seen several revisions based on other peoples’ comments.
- bonoboTP 1y ago
  Basically, for each input length, you can have different runtimes depending on the contents of that input. If you always pick the highest runtime for each length, that gives you a specific function. You can then derive either a lower or an upper bound for that function. Same for the best case. You can state four combinations in their common sense intuition as - even in the worst case, the runtime grows only at most as fast as n^2 (modulo multiplication and addition) - in the worst case, the runtime can grow at least as fast as n^2 - in the best case, the runtime can grow only at most as fast as n^2 - even in the best case, the runtime grows at least as fast as n^2 One can imagine it as not just a single curve on a function plot, but a band, a range. Then the top line of this range can be bounded from above or below, and the bottom can also be bounded from above or below. The common case is when you give a bound for the top curve, from above. How to work this into the article, I don't know, sorry.
  - samwho 1y ago
    I appreciate you taking the time to explain this to me, thank you. I feel like the way I have it is a reasonable, if strictly incorrect, simplification for someone new to the material. When I write these, I have the newly-hired bootcamp grad as my target audience. Someone who has been taught the basics for how to write code for the web and work as a junior within a company, but has no computer science background. I want them to understand enough to make sense of what they see.
    - bonoboTP 1y ago
      Maybe like this: "It's common for an algorithm's performance to depend not just on the size of the input, but also its arrangement. In such cases we typically use big O notation to describe the worst-case scenario. However, note that we may perform similar analysis on the best case or the average case as well." But here: > You may sometimes see the Greek letter "theta", Θ, instead of the letter O in big O notation. This is used when the best and worst case have the same order of growth. We can't use it for bubble sort because the best case is O(n) and the worst case is O(n^2). This is plain false, the worst-case runtime of bubble sort is indeed Θ(n^2). Either delete it, or write about the upper bound / lower bound thing.

samwho 1y ago

It’s okay, you’re not the first to point it out to me! I’d be interested to hear how you would explain it when you’re at a more appropriate device.

IceDane 1y ago
TLDR: Different contexts, different analyses. You can do a best-case, average-case and worst-case analysis. A linear search is O(1) in the best case, for example. Maybe this comes across as nitpicky to some, but that doesn't make the text any less incorrect, unfortunately. It's an extremely common misconception, however, and I would say that a huge proportion of students that go through an introductory course on this subject come out thinking the same thing. > It’s okay, you’re not the first to point it out to me! It would be nice if you corrected it - there are already too many people making this mistake online.
- samwho 1y ago
  So your contention is with the word “always”? It doesn’t always mean worst case? I got told off by someone else for _not_ saying this. I really just want to find the way of describing this that won’t net me comments like yours. It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best.
  - jibal 1y ago
    > I got told off by someone else for _not_ saying this. And what made you think they were right? > I really just want to find the way of describing this that won’t net me comments like yours. Do research. There's a large literature on algorithmic complexity ... maybe start with https://en.wikipedia.org/wiki/Big_O_notation https://en.wikipedia.org/wiki/Big_O_notation > It is very disheartening to spend so much time on something, and really try to do the topic justice, to be met with a torrent of “this is wrong, that’s wrong, this is also wrong.” Please remember I am a human being trying to do my best. non sequitur

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)