Hacker News new | comments | show | ask | jobs | submit login
Say O(n²) Eighty Eight Times Fast (iankelling.org)
6 points by IanKelling on Sept 29, 2014 | hide | past | web | favorite | 3 comments



"O(n^2)" should definitely not have a literal reading involving any words like "algorithm", "efficiency", or "time". This notation is not about algorithms or anything else in computing; it is about the growth of a (mathematical) function.

In computer science, the foremost application of such notation is to the time-complexity function of an algorithm. But there are other applications within C.S., and many more outside it.

OTOH, there is a difference between reading the notation as written, and interpreting the concept. Certainly there is a place in computing for talking about "quadratic time complexity". In such a situation, we might write "O(n^2)". That would be literally read as "(big-)Oh of n squared", but in context it might be telling us something about time complexity, and there isn't anything wrong with reading it that way.

Note: I always say the "big" in "big-O", because standard mathematical notation also includes "little-o", which is also about asymptotic growth rate. Little-o is far less common in C.S., though.


'Ordo n squared' - to pretentious?


> The result is 89 terms which have the same meaning in a conversation (unless your votes/comments say otherwise). And that doesn’t even consider whether to say someting[sic] is O(n²), has O(n²), or is of O(n²).

That has more to do with how the rest of the sentence is constructed, and to some extent the selection of pronunciation of O(n²). e.g., selecting "order n-squared" makes "is of" the natural choice, while "big-oh n-squared" is less grammatically awkward with "is" (arguably, the former example could be "of order n-squared", in which case "is of" is not actually different from "is"). To completely disambiguate, one should specify what the growth is in respect to: time, space, or something else. For example "In the worst case, quicksort is oh of n-squared with respect to time." "Has" should be reserved for when using O(n²) as an adjective, e.g. "Quicksort normally has oh of n log n growth in time."




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

Search: