Time Complexity

Time complexity is the measure of growth of runtime for an algorithm to complete as a function of input size, usually in its worst case scenario. In other words, how bad does an algorithm get if our input size becomes huge. Best and average-case scenarios are also sometimes used, though less common.

Big O

Big O notation is the standard way of denoting time complexity in computer science. More precisely, big O notation standardizes a way of describing the asymptotic growth of a function. Grasping what that is is crucial for understanding time complexity (and CPSC 221).

To describe the growth of a function asymptotically, means that the only thing that we consider when describing the growth of that function are the highest-order terms of that function, usually denoted by $x$, or $n$.

Order (math)

In this context, order (kinda) just means the exponent, so highest-order term is the variable with the highest exponent. So in $f(x)=x^3+x^2+32$, that would be $x^3$.

Constant factors and lower-order terms are ignored. In other words, a function that takes in a parameter $x$ and grows at a rate of $321312x$, is the exact same asymptotically as one that grows at $x/134134$. Therefore, we can say that both of those functions would be $O(x)$.

You can expand that to having any ‘added’ terms, like $x+4$ being the same asymptotically as $x+4000$.

We do this because in computer science, a lot of algorithms are used many, many, times, on sometimes millions of inputs. What we want to consider in cases like these is not exactly how much time a single run through the algorithm would take, but rather how bad it would get if we had to repeat that algorithm millions of times.

There are three mathematical symbols relevant to this, and a literal capital O is one of them. The three are:

• $O$
• $\Omega$ (Omega)
• $\Theta$ (Theta)

$O$

Big O denotes the ‘order’ of a function. For a function to be ‘big O’ of another just means that it grows at a slower or equivalent rate. Keep in mind that in big O notation, the meaning of growth is precise, it’s asymptotic growth, meaning when it tends to very, very large inputs.

For example, if we have a function that grows linearly, say $f_0(x)=x$, and a function that grows quadratically, say $f_1(x)=x^2$, which of the following are true?

• $f_0\in O(f_1)$
• $f_1\in O(f_0)$

Answer

$f_0\in O(f_1)$. $f_0$ grows linearly, so if $x=1$, $f_0(x)=1$. For $x=10$, $f_0(x)=10$. But $f_1$ grows quadratically, when $x=10$, $f_1(x)=100$. Therefore, since $f_0$ grows slower than $f_1$, we have $f_0\in O(f_1)$.

If we have one function $f_0(x)=2x+4$ and one function $f_1(x)=4x+13$, which of the following are true?

• $f_0\in O(f_1)$
• $f_1\in O(f_0)$

Answer

Both. Keep in mind that big O notation discards lower order terms that do not affect the main input of the function, in this case $x$. A function that grows at $2x$ and one that grows at $4x$ are of the same asymptotic order in big O notation, in this case linear growth.

$\Omega$

Omega denotes the opposite of $O$. It represents the lower bound, as opposed to the higher bound of $O$. In other words, an algorithm is $\Omega$ of another if it grows at a faster or equivalent rate than the other. I like to think of it as ‘eclipsing’ another algorithm.

For example, say we have an algorithm whose time complexity can be represented by the function $f_0$ where $f_0(x)=x^3+x^2+2$, and another algorithm represented by $f_1$ where $f_1(x)=x^2+43x+4$. Since the highest order term of $f_0$ is $x^3$, and the highest order term of $f_1$ is $x^2$ we can conclude that $f_0$ dominates $f_1$ in growth asymptotically. In other words, as we previously saw with $O$, $f_1\in O(f_0)$, but also the opposite is true with $\Omega$, and we have: $f_0\in \Omega (f_1)$.

Can you think of any functions that are $\Omega (x)$?

Answer

There are a few forms of functions that have slower growth than linear, and are thus $\Omega (x).$

• Linear functions (remember $\Omega$ is inclusive)
• Logarithmic functions, like $f(x)=\log x$
• Constant functions, like $f(x)=1$
• Reverse linear functions, like $f(x)=\frac{1}{x}$
• Reverse Ackerman (more rare, only really seen in disjoint sets)

$\Theta$

Theta denotes a combination of $O$ and $\Omega$. It represents both the lower and higher bound of a function. In this case, if a function is $\Theta$ of another, it means they have the same asymptotic time complexity.

There are many examples, but one could be the algorithms represented by $f_0(x)=x-24$ and $f_1(x)=343x+67$. In this case, since they both have the same highest-order term, $x$, they are in $\Theta$ of each other. So both $f_1\in \Theta (f_0)$ and $f_0\in \theta (f_1)$ are true.

Amortized Time Complexity

Amortized time complexity is a measure of the time complexity spread over each case, as opposed to a single individual worst case. This is usually used in cases where a specific operation is particularly costly. An example of such use is for insertion into dynamically sized arrays, like C++‘s vector.