A visual introduction to big O notation

Nuances of Big O Notation and Its Common Misconceptions

A significant portion of the discussion revolves around the technical accuracy of the original post's explanation of Big O notation. Several users point out that the article contains inaccuracies and simplifications that can lead to fundamental misunderstandings.

• Big O is Not Always Worst-Case: A primary critique is the assertion that "big O notation always describes the worst-case scenario." Users like IceDane and lordleft clarify that Big O can describe best-case, average-case, or worst-case scenarios. IceDane states, "You can do a best-case, average-case and worst-case analysis. A linear search is O(1) in the best case, for example." umanwizard further elaborates, "The worst-case runtime of quicksort is O(n^2). The average runtime is O(n * log(n))."
• Distinction Between Big O and Big Theta: The article's explanation of Big Theta (Θ) is also flagged as incorrect by bonoboTP. The article states that Big Theta "is used when the best and worst case have the same order of growth." bonoboTP corrects this, explaining, "Big O, Ω, and Θ are ways to describe asymptotic bounds on runtime. You can apply them in best, average, or worst case analyses." bonoboTP also corrects the misconception about bubble sort, stating, "the worst-case runtime of bubble sort is indeed Θ(n^2)."
• Big O as an Upper Bound: Users like blt, tromp, and mfsch emphasize that Big O technically denotes an upper bound, meaning a function grows at most as fast as the given function. This implies that an algorithm with O(n²) complexity is also O(n³), O(n⁴), etc., but the tightest bound is usually preferred for clarity and usefulness. mfsch states, "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”."
• Scope and Definition of Big O: The discussion touches on the broader mathematical definition of Big O, which isn't strictly tied to algorithm analysis. blt points out, "the function x^2 is O(x^3) is a valid sentence in big-O notation, and is true," and mentions its use in Taylor series approximations and statistics. LPisGood also raises a point about how Big O might be interpreted differently in the context of Turing machines, suggesting O(log n) might effectively be O(1).

The Role of Mathematics and Calculus in Understanding Big O

A recurring theme is the debate about the necessity of understanding calculus and more rigorous mathematical concepts to truly grasp Big O notation, especially for those without a formal computer science background.

• Calculus as a Foundation: dawnofdusk argues that a lack of calculus understanding is the root of many common Big O misconceptions, particularly concerning "asymptote" and how constants and subdominant terms can affect practical performance. They state, "every 'common misconceptions about Big O' is because people didn't have the necessary notions in calculus."
• Bridging the Gap for Non-CS Backgrounds: The author, samwho, aims the article at "newly-hired bootcamp grads" and "junior software engineers without math or computer science backgrounds." He believes it's reasonable to provide an introduction that may not be strictly technically correct but imparts useful information for their day jobs. samwho defends this approach, saying, "I think it's reasonable for people to want to have an idea of what big O is for (in software engineering!) without having to have a grounding in calculus."
• Counterarguments on Accessibility: However, users like ndriscoll challenge this, comparing it to engineers ignoring derivatives. ndriscoll asserts, "If you want know what calculus-y words mean, you're going to need to learn calculus. People use calculus-y words to quickly convey things professionally." oooyay echoes this, stating, "You can't really full understand it beyond a facade unless you have a rudimentary understanding of Calculus."

The Nature of Online Discussions and Explanations

The thread also reflects on the dynamics of online technical discussions, criticism, and the challenges of creating accurate educational content.

• The "Well, Actually" Phenomenon: Some users acknowledge that the criticisms can be perceived as overly pedantic or unhelpful "well, actually" comments, even when technically correct. forrestthewoods notes this trend, stating, "This “well ackchyually“ is not particularly helpful."
• Cuningham's Law: bonoboTP offers a perspective on Hacker News culture, citing "Cunningham's Law" (the best way to get the right answer on the Internet is to post the wrong answer) and encouraging the author to view criticism as helpful feedback rather than personal attacks.
• Balancing Accuracy and Accessibility: There's an ongoing discussion about the trade-offs between technical precision and making complex topics accessible to a broader audience. samwho expresses the difficulty in satisfying everyone and the disheartening nature of receiving numerous corrections. ndriscoll and dawnofdusk engage in a debate about whether oversimplification is inherently detrimental, with ndriscoll suggesting that some topics genuinely require more depth than a blog post can provide, while dawnofdusk advocates for more accessible explanations that don't perpetuate inaccuracies.
• The Value of Visualizations: Several users praise samwho's use of "dynamic visualizations" and "interactive visualizations" as being exceptionally helpful for understanding the concepts, with 1zael and primitivesuave specifically highlighting their effectiveness.
• The "Toxic Expert" Dynamic: The discussion touches on the phenomenon of some experts offering criticism in an aggressive or condescending manner, contrasting with more constructive feedback. the_af and arp242 discuss the distinction between helpful correction and the "toxic expert" approach of nitpicking without offering solutions. 0xbadcafebee even identifies as a "Toxic expert" and critiques the blog post's layout and its potential for reinforcing ignorance.

Practical Applications and Real-World Relevance of Big O

The conversation also touches upon how Big O notation is used and perceived in various practical programming contexts.

• Worst-Case Scenarios in Production: tialaramex provides a striking example of quicksort with an O(n²) worst-case being the default in C++ stdlib implementations for years, highlighting that practical usage doesn't always strictly adhered to the "best" case.
• The "Sweet Spot" of N²: Panzer04 and vlovich123 discuss how O(n²) algorithms can be particularly insidious because they are "fast enough to get into production and slow enough to blow up." Panzer04 uses the example of Rockstar wasting five minutes loading GTAV due to an O(n²) algorithm in the startup sequence. svara adds that for many practical purposes, n² implies a program will "computer stops working here."
• Big O's Evolving Relevance: wpollock questions the relevance of Big O in modern hardware with multithreading and caching, suggesting that low-level details can sometimes be more misleading. jonahx counters that Big O was invented precisely to be independent of such details, making it timeless, while acknowledging the importance of constants for smaller N.
• LLMs and Algorithmic Complexity: adinhitlore and lblume discuss using LLMs to generate code with specific complexity requirements, with adinhitlore aiming for "polynomial non-exponential code which isn't n^2 or related" to avoid performance bottlenecks in complex projects. This leads to a brief tangent about LLM capabilities and limitations.

The History and Foundation of Big O

A brief mention of the notation's origins and its place in computer science education is also present.

• Historical Context: lenkite notes that Big O notation was invented by Paul Bachmann in 1894, indicating it's not a recent development.
• Educational Pathways: Users discuss where Big O is typically taught, with some mentioning discrete mathematics classes, algorithm analysis courses, or even osmosis through early programming exposure. fracus notes that in electrical engineering, it felt "hand waved." daemonologist recalls it being a junior/senior year class in university, with an expectation of prior familiarity.