Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one:
I know the x-axis represents some amount of information, and the y-axis represents some amount of time. However, what is the amount of actual time or data represented, does it depend on different types of computers or is it a standard (e.g.) bytes to seconds or KB to minutes?
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.
FindMax(ls)
m <- null
for each x in ls
if x > m
m <- x
return m
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 return m.
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:
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.
The point of the O(.) notation is to do away with the parts of the real world that hinder our understanding of how an algorithm scales, namely because you would get a different graph depending on the computer you use.
You get to pick the units of your X-axis, as long as they accurately measure the size of your input (typically: the size of its binary representation); and the same goes for your Y-axis, whose units measure the amount of computation the algorithm spends on the input. This might be seconds, milliseconds, cycles, ... but usually, we just speak of an abstract time unit, and more precision would require more information on the target architecture, which would defeat the purpose of using O(.).
