Some quick notes on Big O notation.1

How to Determine Running-Time Complexity

Nested Loops

Consider a general sequence of nested loops in which the outer loop is iterated $N$ times and the inner loop is iterated $M$ times. Generally, these will look something like this:

for (i = 0; i < N; i++) {
  for (j = 0; j < M; j++) {

Every time the outer loop executes, the inner loop runs $M$ times. Thus, we expect this function to run in $O(N \cdot M)$, or $O(N^2)$ in the case that $N=M$.

A similar case arises when the inner loop depends on the outer loop. Consider the function

for (i = 0; i < N; i++) {
  for (j = i + 1; j < N; j++) {

Since the outer loop ranges over $0<i<N-1$, while the inner loop ranges from $ N>j>1 $, the total number of operations is given by

which is the sum of the first $N$ natural numbers, and thus this function is also in $O(n^2)$.

Function Composition

Consider a function $ g(n) \in O(n)$ for which the complexity depends on the number of inputs $n$. If this function is embedded within another function $f(m) \in O(m)$ that also depends on another variable $m$, then the composition $(f \circ g) \in O(n \cdot m)$.

Again, in the special case that $n=m$, then $(f \circ g) \in O(n^2)$.

For example, take $f$ to be a loop, and $g$ to be a function called within the loop. Then you wind up with something like this:

  void f(n):
  for (i = 0; i < n; i++) {

The loop iterates $n$ times, and $g$ is called each time. So we have an overall complexity of $O(n \cdot n) \in O(n^2)$.

Note: This method may not always produce the tightest upper bound possible. For more specific cases, tighter bounds on running time can be found by considering the total time spent on the inner loop and outer loop separately, and adding them.

That’s all for today’s post, although I may end up adding more information later! If you have any questions or found this helpful, feel free to comment below.

Links and References

Some great practice problems and explanations: Carl Burch at Hendrix

Leave a comment