How does f(n) < cg(n) specify time?

Question

I have been reading this tutorial on time complexity, and I am a bit puzzled on its explanation of big $O$ notation. It writes:

$O(g(n)) = $ { $f(n)$ : there exist positive constants $c$ and $n_0$ such that $0 \leq f(n) \leq c*g(n)$ for all $n > n_0$.

The way I understand it, $c*g(n)$ denotes $c$ multiplied by $g(n)$. If this is the case, then how does the above expression specify time, and not just that $c*g(n)$ is greater than $f(n)$? Or am I incorrect, and this is some notation I don't understand? My understanding of time complexity is very rudimentary, so forgive me if this is just a stupid mistake on my part.

Answer 1

How does f(n) < cg(n) specify time?

It doesn't. Bachmann-Landau notation is simply a handy way to compare the growth-rate of functions. It doesn't say anything about what those functions mean, and we can be pretty sure that Bachmann wasn't thinking about computers when he came up with it in 1894.

What meaning you assign to those functions is up to you. For example, when analyzing comparison-based sorting algorithms, we typically take $n$ to be the number of elements in the collection and $f(n)$ to be the number of comparisons, or the number of swaps, or the number of comparisons and swaps.

Note also that all of this is always relative to a machine model or a cost model.

As a very simple example, if I were to ask you what is the algorithmic worst-case step complexity for copying a list, you would say $O(n)$. But actually, the correct answer would be "I can't tell you that because you haven't specified the machine model". Because, for example, in a Turing machine, copying a list is $O(n^2)$, because for each element being copied, the head of the TM has to drive further and further and further to reach the end of the list to write the next element.

Answer 2

Saying that the running time of an algorithm is in $O(g(n))$ gives, as you noted, only an upper bound. Moreover, the upper bound is given with the constants $c$ and $n_0$ unknown. So yes, it is a rather weak information about the running time.

The unspecified constant $c$ can contain the information about the real cost of the basic operations of the algorithm, which can be unknown and/or variable between runs, but still known to cost an amount of time that is bounded. The unspecified constant $n_0$ reflects that the bound given refers to large sizes of the input (or whatever parameter $n$ is representing).

Other symbols are used to give other types or more precise information about the running time.