Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

That's incorrect. The /mathematical/ definition means that it's the upper bound. I.e. yes, the set of all functions of O(N) is a subset of the set of all functions O(N^2). So you could say Quicksort is O(N^100) and still be technically correct.

However, the big-O notation does NOT specify anything about worst/avg/best-case complexity of a given algorithm. That should still be defined in the analysis.

You mixed up those two slightly different concepts.



Consider applying for YC's Winter 2026 batch! Applications are open till Nov 10

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: