Complexity Analysis

Complexity Functions

To understand complexity analysis notations, we must understand how functions grow. In the preceding examples, we stated no requirements about the functions we used to model efficiency. At this point, we've seen enough to handle formality.

complexity function. Let ${f}$ be a function from ${\reals}$ to ${\reals}$ with ${x \in \reals.}$ Then ${f}$ is a complexity function if, and only if, the following axioms are true: (1) There exists a number ${n \in \reals^+}$ such that, if ${x \ge n,}$ then ${f(x) \in \reals.}$ (2) There exists a number ${m \in \reals^+}$ such that, if ${x \ge m,}$ then ${f(x) \ge 0.}$

Complexity analysis — for our purposes — is limited to the class of functions above. We do so for several reasons. First, resources like time and memory are easiest to interpret in terms of positive numbers. Second, we could make things even easier by just limiting ourselves to the natural numbers, but then we'd exclude swathe of useful functions — ${f(n)=\lg n,}$ ${f(n)=\sqrt n,}$ and even the sinusoids ${f(n)=\cos(n), f(n)=\sin(n), etc.}$ So, we restrict complexity analysis to real-valued functions.

Requirement (1) in the definition ensures that we won't run into functions that never get defined on the reals when given positive arguments. For example, ${f(n) = \sqrt{-n}.}$ Requirement (2) is similar in spirit; we don't want to work with functions that never become positive. It's perfectly fine for the function to return negative values (e.g., ${f(n) = \lg n}$), but it's not ok for the function to always return negative values (e.g., ${f(n) = -n^2}$).

Big O

big o. Given the complexity functions ${f: \reals \to \reals}$ and ${g: \reals \to \reals,}$ if there exists a constant ${\C \in \reals^+}$ and a threshhold ${t \in \reals}$ such that, for all ${x \geq t,}$ both ${f}$ and ${g}$ are defined with ${\abs{f(x)} \le \C \cdot g(x),}$ then there exists a class of functions called big O of ${g,}$ denoted ${\bigO{g},}$ with ${f \in \bigO{g}.}$

This definition has a few moving parts. But before we examine those parts in detail, let's get a big picture view first. The letter ${{\cal{O}}}$ comes from the German word ordnung, which means order of approximation. This gives us a hint as to what ${\cal{O}}$'s purpose is.

Next, it's helpful to recall what a function is: It's a set of tuples. Given that we're working with complexity functions, we're looking at sets of pairs — objects of the form ${(x,y),}$ where ${x}$ and ${y}$ are real numbers. Say we had two complexity functions, ${f: \reals \to \reals}$ and ${g : \reals \to \reals.}$ Both of these functions have the same domain and the same codomain, and again, both are sets of pairs. Suppose ${f}$ contains a pair ${(x_0,y)}$ and ${g}$ contains a pair ${(x_0,b).}$ We're using ${y}$ instead of ${f(x_0)}$ and ${b}$ instead of ${g(x_0)}$ to make things clearer. Because ${y}$ and ${b}$ result from the same argument ${x_0}$ and both ${y}$ and ${b}$ are real numbers, we can compare them. And if we did, the trichotomy law tells that there are three possible outcomes, only one of which is true:

Now, what big O says is this: If we ever see that case 1 is true and stays true for all the ${x}$s after ${x_0,}$ or if we ever see that case 2 is true and stays true for all the ${x}$s after ${x_0,}$ then we can use ${g}$ as an approximation of ${f.}$ Why? Because ${g}$ contains all of ${f}$'s values eventually.

So why exactly do we write ${f \in \bigO{g}?}$ Because we want to emphasize that ${f}$ is an approximation. The notation ${\bigO{g}}$ represents a collection of functions — called a class of functions — whose ${y}$s are, at some point, always less than or equal to ${g}$'s ${b}$s. Writing ${f \in \bigO{g}}$ is akin to hedging our bets — we're not saying that ${f}$ is ${g,}$ we're saying that ${f}$ is just one of the many functions covered by ${g.}$ That second half is why describe this as hedging — there may actually be another function ${h,}$ that's a much better approximation. That is, ${f \in \bigO{h}}$ and ${\bigO{h} \subseteq \bigO{g}.}$ To illustrate, consider the following function graphs:

example. Let ${f(x)=x^2}$ and ${g(x)=x^3.}$ Then ${f \in \bigO{x^3},}$ because if ${x \gt 2,}$ then ${x^3 \gt x^2.}$

example. Function definitions do not always determine growth rates. For example, given ${f(x) = x^2+1}$ and ${g(x)=x^2,}$ if ${C=2}$ and ${t=2,}$ then ${2x^2 \gt x^2 + 1.}$ Or, more explicitly, ${x^2 + x^2 \gt x^2 + 1.}$ thus, we have ${f \in \bigO{x^2}}$ when ${f(x) = x^2 + 1}$ and ${g(x) = x^2.}$

Having seen some examples, it's helpful to put the complexity functions in perspective. We do so with the table below. The times correspond to the approximate amount of time needed to completely execute an algorithm of order ${T.}$