Big O

Musings from a self taught developer

Created: Mar 29, 2020

Last Updated: Mar 29, 2020

Lesson

Big O is a way to describe the rate of growth of an algorithm based on the input. Specifically, Big O is the upper bound runtime of and algorithm. It is defined as

f(n)O(g(n))f(n)cg(n) \mathrm{f}\left(\mathrm{n}\right)\in\mathrm{O}\left(\mathrm{g}\left(\mathrm{n}\right)\right) \rightarrow \mathrm{f}\left(\mathrm{n}\right)\le\mathrm{\mathrm{c}\mathrm{g}\left(\mathrm{n}\right)}

where (c>0)(c > 0) and (n0)(n \ge 0)