Complexity Analysis & Big(O)

Why do I need to know this?

This was a question I grappled with for a while. Eventually, I came to realize that the reality of the situation is that, even though you will almost certainly NOT be using complexity analysis in your day to day, you need some way to represent these abstract ideas, even if you recognize, mentally, that some ways of writing code are just better (and more clever) than others.

What counts as a step?

A step is one primitive operation, something the computer does in a fixed amount of time no matter how big the input is. Assigning a variable, doing arithmetic, comparing two values, indexing into an array, and returning from a function all count as one step each. Whether sum += i is one step or two is a convention, so pick one & stay consistent.

The only thing worth memorizing is the for loop. for (int i = 0; i < n; i++) costs 2n + 2 steps before the body even runs: the i = 0 happens once, the i < n check happens n + 1 times (n times it’s true, once it’s false), and the i++ happens n times. That’s 1 + (n + 1) + n.

int func1(int n) {
  int sum = 0;                    // 1 step
  for (int i = 0; i < n; i++) {   // 2n + 2 steps
    sum += i;                     // 1 step, n times = n
  }
  return sum;                     // 1 step
}
// total: 1 + (2n + 2) + n + 1 = 3n + 4

Nest a loop inside of it and the inner loop’s cost gets paid on every pass of the outer one:

int func2(int n) {
  int sum = 0;                      // 1 step
  for (int i = 0; i < n; i++) {     // 2n + 2 steps
    for (int j = 0; j < n; j++) {   // n * (2n + 2) = 2n² + 2n steps
      sum++;                        // n * n = n² steps
    }
  }
  return sum;                       // 1 step
}
// total: 1 + (2n + 2) + (2n² + 2n) + n² + 1 = 3n² + 4n + 4

Those exact numbers depend on what you decided counts as a step, and someone else’s convention would land on a slightly different answer. That’s fine, because the next section throws most of it away. All that survives is that func1 grows linearly and func2 grows quadratically.

The deets

First, common orders of functions (top down, from best-worst)

The relationship that complexity analysis is trying to create is that which tells you how an algorithm’s time/space scales as input grows. In other words, when looking at an algorithm, you’re measuring two main things: the time it takes for the algorithm to complete, and how much space the algorithm needs.

What we can drop & ignore

During complexity analysis, you can make a couple of big leaps.

You can drop constants from equations.

For example: $3n^2$ + $7n$ + 42 = $O(n^2)$

$f(n)$ = $3n^2$ + $7n$ + 42

$g(n)$ = $O(n^2)$

g(n) is a simpler function you pick to stand in for the growth of f(n). It isn’t the growth itself.

You can drop constants because complexity analysis measures growth. I.e. how the cost grows as the input gets huge, and a constant factor doesn’t change that growth. It only changes the starting height.

Example: Say algorithm A takes 100n steps and algorithm B takes n² steps.

B wins at small sizes, they tie at 100, and after that A wins by a wider margin every time. No constant you put in front of n can stop n² from catching up eventually. If you changed A to 1000n, the crossover would just move to n = 1000. The shape of the curves is what decides who wins in the end.

There are a couple of logistical reasons we can do this:

• Constants depend on the several parts of the machine that are irrelevant to the goal of Big-O, which is only meant to describe the algorithm, not your hardware.
• Constants are a moving target. One “step” might be one instruction or ten, depending on how you count. Counting can give a different answer for every counting convention, and the growth rate is the only thing they all agree on.
• Doubling the input: With 5n, doubling the input doubles the work. With 5n², it quadruples the work. The 5 never shows up in that comparison.

Ignore lower order terms

$n^2 + n + 1 = O(n^2)$

$n^2 + \log n + 1 = O(n^2)$

Lower order terms get dropped because they stop mattering. Here’s $3n^2 + 7n + 42$ as n grows, and how much of the total is just the $n^2$ term:

By the time n is a million, everything except the $n^2$ term is a rounding error. To figure out which term is the highest order, use the table of orders from earlier: whichever one is lower down in the table wins. So $n^2$ beats $n \log n$ beats $n$ beats $\log n$ beats $1$.

Ignore the coefficient of the highest order term

$3n^2 + 7n + 42 = O(n^2)$

That 3 is a constant multiplier, so it goes for the same reason as above. Just be careful about where the constant is. It only disappears when it’s multiplied out front. If it’s in an exponent or a base, it stays: $2^n$ and $3^n$ are different orders of growth, and so are $n^2$ and $n^3$.

Summary

Generally, for exams, having log & power identities will be extraordinarily helpful in order to see how different complexities are actually equivalent to each other.

Log Identities

Power Identities

Big-O, Big-Θ, and Big-Ω

Big-O, Big-Θ, and Big-Ω are three ways to bound a function. A bound is just a simpler function that sits above, below, or right on top of yours once n is big enough.

The $c$‘s and $n_0$ are positive constants that you get to pick. The $c$ is the “drop constants” rule, since any multiplier gets absorbed into it, and $n_0$ is the “big enough” part, since $f(n)$ is allowed to break the rule for small inputs.

Example with $f(n) = 3n^2 + 7n + 42$:

• Upper: for $n \ge 1$, $7n \le 7n^2$ and $42 \le 42n^2$, so $f(n) \le 52n^2$. Pick $c = 52$ and $n_0 = 1$, which makes $f(n) = O(n^2)$.
• Lower: $f(n) \ge 3n^2$ for every $n$, so pick $c = 3$ and $n_0 = 1$, which makes $f(n) = \Omega(n^2)$.
• Tight: it’s both, so $f(n) = \Theta(n^2)$.

It’s also true that $f(n) = O(n^3)$ and $f(n) = \Omega(n)$, since an upper bound only has to be above you and a lower bound only has to be below you. They’re just useless statements, so by convention you give the tightest bound you can.

Everyone says Big-O when they mean Big-Θ. That’s fine in conversation, but on an exam, use whichever one the question actually asks for. Also, Big-O does NOT mean “worst case”. It’s a bound on a function. Which function you’re bounding is a separate question, and it’s the next section.

Best, worst, and average case

The bounds above describe a function, but the cost of an algorithm often depends on which input of size n you hand it, not just how big it is. Best, worst, and average case are about which input you got.

int linear_search(const std::vector<int>& vec, int target) {
  for (int i = 0; i < vec.size(); i++) {
    if (vec[i] == target) { return i; }
  }
  return -1;
}

Each case is its own function, so each one gets its own $O$, $\Omega$, and $\Theta$. The best case of linear search is $\Theta(1)$ and the worst case is $\Theta(n)$. When someone gives you a complexity with no case attached, they almost always mean worst case. The same goes for duplicate_nested below: best case is $O(1)$ (the first two numbers match), worst case is $O(n^2)$.

Average case needs an assumption about what inputs are likely, like “the target is equally likely to be anywhere.” Don’t confuse it with amortized complexity, which is next.

Amortized complexity

Some operations are cheap almost every time and expensive once in a while. Amortized complexity is the cost per operation once you spread the expensive ones across the cheap ones.

Think of a cell phone bill. Say it’s $50 a month, except in January you also buy a $600 phone. The bill is spiky, but over the year you paid $1,200 for 12 months, so it works out to $100 a month. That $100 is the amortized cost.

The classic example is std::vector::push_back. Most pushes are O(1): drop the element in the next free slot. When the array is full, though, it has to allocate a bigger one and copy all n elements over, which is O(n). How much bigger decides everything:

Doubling wins because after a copy of k elements, you get k cheap pushes before the next resize. The expensive copy gets paid off by the cheap pushes that follow it, same as the phone. Adding a fixed amount doesn’t work, because the copies keep getting bigger while the gap between them stays the same.

Amortized is a guarantee about a sequence of operations, whatever they are. Average case is about a typical input and leans on probability.

Complexity analysis in action

For example, let’s take a really simple problem: “Is there a duplicate number in my array?” As simple as this question is, the consequences for how you solve this problem can be vast. I’ll get into the nitty gritty of Big O later, so just bear with me through this example:

Vector: [1, 2, 3, 4, 5]

cursor1 = 0, checks against:
   v
  [1, 2, 3, 4, 5]
      ^  ^  ^  ^  (cursor2 goes 1→4)

cursor1 = 1, checks against:
      v
  [1, 2, 3, 4, 5]
         ^  ^  ^  (cursor2 goes 2→4)

cursor1 = 2, checks against:
         v
  [1, 2, 3, 4, 5]
            ^  ^  (cursor2 goes 3→4)

As code, this comes out as:

bool duplicate_nested(std::vector<int> vec) {
  for(int cursor1 = 0; cursor1 < vec.size(); cursor1++) {
    for (int cursor2 = cursor1 + 1; cursor2 < vec.size(); cursor2++)
      if (vec[cursor1] == vec[cursor2]) { return true; }
  }
  return false;
}

While this is a valid way to solve the problem, it’s actually one of the worst ways to do so. Why? Because for every item in the array, you’re checking it against every other item in the array. This means that if you have 10 items, you could be doing up to 100 checks. If you have 100 items, you could be doing up to 10,000 checks. If you have 1,000 items, you could be doing up to 1,000,000 checks. This is a classic example of an algorithm with O(n²) time complexity.

“So, what’s a better way?” Your Grandmother asks at the dinner table. Great question, Grandma! A better way to solve this problem is to use a data structure that A) Doesn’t allow duplicates, and B) Has fast lookup times. A std::unordered_set in C++ is perfect for this. Here’s how you could implement it:

bool duplicate_simple(std::vector<int> vec) {
  std::unordered_set<int> seen_values;
  for (int nums : vec) {
    if (seen_values.count(nums)) { return true; }
    seen_values.insert(nums);
  }
  return false;
}

#whatdatmean

When you insert a number, it runs it through a hash function that converts it to an index (like hash(42) = 7). It stores the number at that index in an internal array. We’ll come back to hashing way later, but all you need to know for now is that when you check if (seen.count(num)), it hashes num again, jumps directly to that index, and checks if it’s there.

Because of allllllat, this works out to about O(n) time complexity, because for each of the n items in the array, you’re doing a constant time operation (hashing and checking/inserting into the set).

If you want to be a fucking chad, you could also just set a vector to a set & compare the sizes:

bool duplicate_cast(vector<int>& nums) {
  unordered_set<int> s(nums.begin(), nums.end());
  return s.size() != nums.size();  // if sizes differ: dupes exist
}

This method also runs in O(n) time, but is just cleaner code. It’s not necessarily better for space, since you’re still using extra space for the set, but it’s a nice one-liner.

Measuring it for real

Everything above is a prediction. You can check it by running the code and timing it with std::chrono:

#include <chrono>

auto start = std::chrono::steady_clock::now();
duplicate_nested(vec);
auto stop = std::chrono::steady_clock::now();

auto ms = std::chrono::duration_cast<std::chrono::milliseconds>(stop - start).count();

Use steady_clock, since it can’t jump backwards the way the system clock can. Then compare against the prediction: if duplicate_nested is O(n²), doubling n should make it take about 4x as long. If it’s O(n), about 2x. If you doubled n and the time barely moved, or went up by 8x, either your analysis or your code is wrong.

A few things will ruin your measurements. Compile with optimizations on (-O2), but make sure you actually use the result, because the compiler is allowed to delete work that has no effect. Run it several times, since other programs on your machine add noise. Use inputs big enough to take more than a few milliseconds, or you’re just timing the clock.

When the numbers disagree with your prediction, two tools help you figure out why:

• perf shows where your program spends its time, down to the function (perf record, then perf report).
• valgrind has a few tools. callgrind counts instructions instead of seconds, so it gives the same answer every run. massif shows how much heap memory you’re using over time, which is the space half of complexity analysis.