Big-O notation

It would be convenient to have a form of asymptotic notation that means “the running time grows at most this much, but it could grow more slowly.” We use “big-O” notation for just such occasions.

If a running time is O(f(n)), then for large enough n, the running time is at most k⋅f(n), for some constant k. Here’s how to think of a running time that is O(f(n)):

We say that the running time is “big-O of f(n)” or just “O of f(n)”. We use the big-O notation for asymptotic upper bounds, since it bounds the growth of the running time from above for large enough input sizes.

Leave a Reply

Your email address will not be published.