We use Big-O notation to describe how “fast” an algorithm runs with respect to the size of the input in the worst case scenario. This input can be a number, a list of numbers, a matrix, etc. By fast, it essentially translates to number of steps the algorithm takes based on the size of the input in the worst case scenario.
I should start by describing the difference between an algorithm and an implementation of an algorithm. An algorithm is just a set of instructions that solves a problem. An implementation of an algorithm is code that is run on hardware that actually performs the set of instructions.
Suppose we have a simple problem, “given a list of numbers of arbitrary size and in no particular order, find the maximum value in the list”. We solve this problem with an algorithm. Below is a solution to the problem.
m <- null
for each x in ls
if x > m
m <- x
To analyze how good this solution is, we to find what the worst case is for this algorithm to handle. For this algorithm, the worst case would be a sorted list in ascending order. This is because the if statement will always be true (adding more steps).
Let $n$ be the size of the input list. Now let’s count the number of steps our algorithm takes to complete (in the worst case). The initialization is 1 step (
m <- null). The for loop will loop $n$ times. The amount it does inside the loop will be 2 steps (1for the if statement check and 1 for its body). Finally, 1 step for
Let $T(n)$ be the worst case runtime for our algorithm. From above we have $T(n) = 1 + 2*n + 1 = 2*n + 2$.
This is where big-O notation will help us. We need to find a function $g(n)$ grows at a similar rate as $T(n)$; this function will be our upper bound. In other words, we need to find a function $g(n)$ where $T(n) leq k*g(n)$ for all $n geq n_0$.
Let’s try $g(n) = 1$. Here we see that no matter what $k$ we try, $T(n)$ will always be greater at some point; more precisely, when $n>k$ then $T(n) > k*g(n)$. This means $g(n) 1$ is not big enough.
Let’s try $g(n) = n$. Here we see that if we choose $k geq 3$ and $n_0 = 1$, $k*g(n) geq T(n)$ for $n geq n_0.
What we proven is that $T(n)$ is bounded above by $g(n) = n$. This means that $T(n) in O(g(n))$; in other words $T(n) in O(n)$. Notice how I used $in$ instead of $=$. This is because $O(g(n))$ is the set of all functions that are bounded above by $g(n)$. However, it is common practice to abuse the notation $T(n) = O(n)$.
The purpose of this example is to show you the context of big-O notation. Big-O notation is purely abstract in that we count the number of steps of the algorithm, not the amount of time (in seconds) it takes to complete. If we implement this algorithm in a program language (like C/C++ or Java) and run it on the computer, then we have many more factors to consider:
- Number of cores of CPU
- Clock speed of CPU
- Amount of memory
- I/O speed of the input
- Language specific performance issues (e.g. C/C++ faster than Java)
None of these factors describes how well an algorithm performs; rather they show how well the implementation performs. See Big O Notation for an example and more information.