1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ The link to the graph is dangling. $\endgroup$ – Yuval Filmus Dec 23 '20 at 14:59
1
$\begingroup$

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:

  • 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)
  • etc.

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.

$\endgroup$
0
$\begingroup$

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(.).

$\endgroup$
2
  • $\begingroup$ For clarification, the x-axis is usually some form of bits/bytes and the y-axis is some form of seconds/ms? $\endgroup$ – VINCENT ZHANG Dec 23 '20 at 3:23
  • $\begingroup$ Yes indeed, "some form of". $\endgroup$ – Anthony Labarre Dec 23 '20 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.