Asymptotic Notation

Introcduction

There is no single data structure that offers optimal performance in every case. In order to choose the best structure for a particular task, we need to be able to judge how long a particular solution will take to run. Or, more accurately, you need to be able to judge how long two solutions will take to run, and choose the better of the two. We don't need to know how many minutes and seconds they will take, but we do need some way to compare algorithms against one another.

Asymptotic complexity is a way of expressing the main component of the cost of an algorithm, using idealized (not comparable) units of computational work.

The O Notation

The O (pronounced big-oh) is the formal method of expressing the upper bound of an algorithm's running time. It's a measure of the longest amount of time it could possibly take for the algorithm to complete.

More formally, for non-negative functions, $f(n)$ and $g(n)$, if there exists an integer $n_0$ and a constant $c > 0$ such that for all integers $n > n_0$, $f(n) \leq cg(n)$, then f(n) is Big O of g(n). This is denoted as $f(n) = O(g(n))$. If graphed, g(n) serves as an upper bound to the curve you are analyzing, $f(n)$.