What do f(x) and g(x) represent in Big O notation?

Question

I have been reading about Big O notation. People writing about Big O often use the terms $f(x)$ and $g(x)$. For instance, I often see people write things like $f(x) = O(g(x))$ or $f(x) \in O(g(x))$. Obviously $f(x)$ is the running time of the given algorithm we are comparing against infinity, but what does $g(x)$ represent?

Answer 1

Summary: $f$ and $g$ are typically functions, and $f$ is typically the runtime and $g$ is typically the asymptotic complexity of $f$. But if any of this is unclear from the description, I think it is best to either find another explanation, or to forget about application domains and intuitions for a second and go back to the definitions.

---

They're both functions. The fact that they are named "f" and "g" is probably due to the usual naming convention of functions, just like "x", "y" and "z" are usual names given to variables.

In this context, $f(x)$ is often the runtime of the algorithm under question, while $g(x)$ is used to denote the asymptotic complexity of $f(x)$; so $f(x) \in O(g(n))$ (or, $f(x) = O(g(n))$). But, convention or not, what $f$ and $g$ are, and they're relation to each other (if any), should be clear and unambiguous from the explanation. Not something that the reader has to guess based on what it usually means. (And the reader should have the mathematical maturity that is necessary to understand the concept.)

Personally, when I am confused about terms and names that are being used, I like to try to forget everything that the terms and names are ultimately used to represent. In computer programming, big-o is often used to describe algorithms. But big-o notation itself abstracts such things away; it is only about functions and their relation to each other. Forget about "runtime", "complexity" or anything else that has to do with the intended application of the notation.

Here is an example:

Let $f$ and $g$ be two functions defined on some subset of the real numbers. One writes

$f(x) = O(g(x))$ as $x \to \infty$,

if and only if there is a positive constant $M$ such that for all sufficiently large values of $x$, $f(x)$ is at most $M$ multiplied by the absolute value of $g(x)$. That is, $f(x) = O(g(x))$ if and only if there exists a positive real number $M$ and a real number $x_0$ such that

$|f(x)| \leq M \cdot |g(x)|$ for all $x \geq x_0$.

We see that $f$ and $g$ are functions. Together with all the variables used, and the relations between them, what $f(x) = O(g(x))$ means is as clear as you might reasonably expect from a Wikipedia article on a mathematical topic. We don't have to consider what this notation is supposed to be used for, and neither what those functions are even supposed to represent/model. Now, going back to the application domain of algorithm analysis; can we use this notation to describe algorithms? Yes, since runtimes of algorithms are just functions on real numbers. Then what does it mean when $f(x) = O(g(x))$, in the context of algorithm analysis? If $f(x)$ is the runtime of the algorithm, then this notation means that $f(x)$ (a runtime) does not grow more quickly than a multiple of $g(x)$, for sufficiently large $x$. That's all from reading from the definition, and interpreting $f(x)$ as a runtime.

Pitfalls of convention

Sometimes, conventions can be misleading. In fact, we've seen a "violation" of a usual mathematical convention in this post.

$f(x) = O(g(n))$

Here, the $=$ sign is used. At least for us non-mathematicians, we are used to this sign denoting a sort of equality between two things. This usually means that the two things are of the same type, e.g. they are both real numbers, and that they are equal in some sense. In particular, $=$ is often an equivalence relation. But this is not the case of this particular use of the $=$ sign. First of all, $f(x) = O(g(n))$ does not mean that $f(x)$ and $g(x)$ are equal: the closest "normal" relation to this is "$f(x)$ is less than or equal to $g(x)$", which obviously has nothing to do with equality (except as a special case). Secondly, $f(x)$ and $O(g(x))$ are not even of the same type: $f(x)$ is a function, while $O(g(x))$ is a class of functions. (An alternative notation to $f(x) = O(g(x))$ is $f(x) \in O(g(x))$, which I used in the beginning. It is arguably more "honest".)

Answer 2

A statement like "$f \in O(g)$" types and binds the identifiers $f$ and $g$ by the definition of $O$. So you really have to look at the definition of $O$, e.g. here. You'll see that both the argument of $O$ and its elements (since $O(.)$ is a set) are functions.

Once you agree that this makes sense, it does no longer matter¹ whether you write $f \in O(g)$, $u \in O(a)$ or $\mathrm{Jack} \in O(\mathrm{Martha})$. Using $f$, $g$ and $h$ for "generic" functions is a convention carried over from mathematics; in CS you also find $T$ in the context of algorithm analysis (representing a runtime function).

For more reading on Landau notation, I recommend our reference questions and the many posts tagged landau-notation we have around.

---

1. Granted, disregarding conventions tends to confuse people.

Answer 3

$f(x)$ and $g(x)$ are functions. $f$ typically models the time an algorithm takes to work on an input of size $x$. When we say $f(x) = O(g(x))$, what we mean is approximately "the time taken by the algorithm to work on an input of size $x$ grows no more quickly than a multiple of $g(x)$ for sufficiently large $x$."