Comment

Comment by sparkie

The misconception is mixing up notations. Using Big-O for the upper bound has been the norm for describing algorithms for at least half a century.

In Knuth's description[1] of Big-O notation (and related variants), from 1976, he starts out by saying:

    Most of us have gotten accustomed to the idea of using the notation O(f(n)) to stand for any function whose magnitude is upper-bounded by a constant times f(n) , for all large n .
Emphasis on upper-bounded. He goes on to describing other notations: Big-omega, for a lower bound, and so forth.

[1]:https://danluu.com/knuth-big-o.pdf

parent sparkie 1 year ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton