Polynomial Algorithms

In the previous lesson, we looked at the cost of operations. We learned that not all operations are created equal; fetching data from the CPU cache is effectively free, while fetching data from main RAM is incredibly expensive.

Factors like locality and caching determine how expensive each operation is, whilst algorithm analysis focuses how many of those operations are required to complete a task.

Big O notation is a high level classifications of how the time required to complete an algorithm changes based on how much data needs to be handled. It's the answer to questions like: "if the number of users doubles, does my system still perform the same, or does it get slower? And if it gets slower, by how much?"

When we analyze algorithms, this idea of the "amount of data", the "input size", or the "number of objects" an algorithm needs to handle is denoted by the variable $n$ or $N$.

For example, if we want to find a specific user in our collection, the amount of work we need to do might depend on the number of users, $n$, that is in our collection.

Most algorithms fall into a category called polynomial. This means the runtime is proportional to $n$ raised to some power $k$. Mathematically, this looks like $O(n^k)$. In polynomial time, $k$ is a constant, like $0$, $1$, $2$, and so on.

Constant time is the gold standard of algorithmic efficiency. It means the execution time is independent of the input size. Whether you have ten elements or ten billion, the code takes the same approximate amount of time to complete.

In our polynomial model, this is $n^0$. Since any number to the power of $0$ is $1$, we write this as $O(1)$.

The classic example of this is accessing an element in an array (or std::vector) by its index.

1#include <vector>
2#include <iostream>
3
4void PrintFirstElement(const std::vector<int>& Data) {
5  if (Data.empty()) return;
6
7  // This operation takes the same time regardless
8  // of whether Data has 1 element or 1,000,000.
9  std::cout << Data[0] << "\n";
10}

Why is this constant? Because of the contiguous memory layout we discussed in the intro.

The compiler knows the memory address where the vector starts, and it knows the size of each element. To find the element at index i, it simply performs one calculation:

This is a single instruction for the CPU. It doesn't need to "search" for the element; it teleports directly to it. This is why we prefer contiguous containers like std::vector whenever possible - they unlock $O(1)$ access patterns.

Linear time means the work grows in direct proportion to the input. If we double the data, we double the amount of work our algorithm needs to do.

In our polynomial model, this is $n^1$, or simply $O(n)$.

This is the complexity of "touching every element." If you need to print every player's name, or sum up a list of transaction values, you are doing $O(n)$ work.

1#include <vector>
2#include <iostream>
3
4void PrintAll(const std::vector<int>& Data) {
5  // A simple loop is the hallmark of O(n)
6  for (int Value : Data) {
7    std::cout << Value << "\n";
8  }
9}
10
11bool Contains(const std::vector<int>& Data, int SearchKey) {
12  // Even though this might return early, in the
13  // worst case we have to check every element.
14  for (int Value : Data) {
15    if (Value == SearchKey) return true;
16  }
17  return false;
18}

Linear algorithms are the workhorse of modern computing. Remember, CPUs are designed with prefetchers - components that predict what memory you will need next.

When you iterate linearly through a std::vector, the access pattern is perfectly predictable. The prefetcher pulls data from RAM into the L1 cache before your code even asks for it.

Because of the realities of hardware, a linear scan over a array is often faster than theoretically superior algorithms, particularly for small to medium datasets.

Quadratic time is where things start to get dangerous. This complexity occurs when the work grows proportional to the square of the input. If you double the data, the work quadruples. This is a quadratic algorithm - $O(n^2)$.

This typically happens when you nest loops - processing the entire collection for each element in the collection. A classic example is checking for collisions between all entities in a game, or checking for duplicates in an unsorted list.

1#include <vector>
2#include <iostream>
3
4void FindDuplicates(const std::vector<int>& Entities) {
5  // Outer loop: n iterations
6  for (size_t i = 0; i < Entities.size(); ++i) {
7
8    // Inner loop: n iterations
9    for (size_t j = 0; j < Entities.size(); ++j) {
10
11      // We perform this check n * n times
12      if (i != j && Entities[i] == Entities[j]) {
13        std::cout << "Duplicate detected!\n";
14      }
15    }
16  }
17}

To visualize this, imagine a grid. If you have a list of 5 items, a linear algorithm walks a line of 5 steps. A quadratic algorithm has to fill in a $5 \times 5$ grid, performing 25 operations.

If $n$ increases, linear algorithm tend to scale in a controllable way, whilst the "grid" of work required of a quadratic algorithm explodes.

These quadratic algorithms are when we begin to enter the danger zone. An algorithm that feels instant when testing can bring systems to a crawl as $n$ gets larger.

Naive Solutions

Our previous algorithm to find duplicates in a collection is an example of a "naive" or "brute force" solution. The same problem can be solved in many different ways. The following solution removes the nested-loop interaction:

1#include <vector>
2#include <iostream>
3#include <unordered_set>
4
5void FindDuplicates(const std::vector<int>& entities) {
6  std::unordered_set<int> seen;
7  for (int e : entities) { // O(n)
8    if (seen.contains(e)) { // O(1)
9      std::cout << "Duplicate detected!\n";
10    }
11    seen.insert(e); // O(1)
12  }
13}

The total complexity here is $n$ multipled by the constant costs of contains() and insert(). And, since Big O ignores multiplicative constants, we now have a linear solution.

For large values of $n$, this is likely to be an improvement over our initial attempt, as long as the additional memory required for the seen container isn't problematic.

We've now seen the three most common types of polynomial algorithms:

1. Constant: $O(n^0)$, usually written as $O(1)$
2. Linear: $O(n^1)$, usually written as $O(n)$
3. Quadratic: $O(n^2)$

This pattern continues. We can have cubic algorithms - $O(n^3)$, quartic algorithms - $O(n^4)$, and so on.

It is quite rare that the algorithms we create to solve real-world problems fit exactly into these equations. For example, an algorithm might require $50n^2$ operations. Another might require $n^2 + 10n + 30$ operations.

Big O notation simplifies things to just the core classification - both of these algorithms would be categorized as $O(n^2)$. This simplification allows us to communicate and compare approaches more simply.

Specifically, Big O makes the following simplifications:

Treat All Operations as Equal

As we've seen in the previous lesson, some operations can take much more time than others, particularly if the required data isn't in the cache. To keep things simple, Big O ignores that. It assumes all operations are equally expensive.

Ignore Constants

One algorithm might require $n + 100$ operations whilst another might require exactly $n$. We ignore the additive constant - both these algorithms are linear - $O(n)$

One algorithm might require $50n$ operations whilst another might require $n$. We also ignore multiplicative constants - these algorithms are still both linear - $O(n)$

Only Include the Dominant Term

One algorithm might require $n^2 + n$ operations whilst another might require $n^2 + 50$. As we saw in the graphs above, the term with the highest order (that is, the largest exponent) dominates the behavior of the function as $n$ increases. So, both of these are classified as quadratic - $O(n^2)$

Remember, the algorithm we use to work with our data is intrinsically linked to how that data is structured. The physical shape of our data sets the speed limit for how fast a task can be accomplished.

Consider the simple task of finding the last element in a collection. If our data is stored in a contiguous array (like std::vector), finding the element at the last index, or any index, is a simple arithmetic calculation based on where the array starts in memory and the size of each element.

It doesn't matter if the array has 5 items or 5 billion; the CPU performs one calculation and jumps instantly to the end. This is a constant time, $O(1)$ algorithm.

However, if your data is stored in a linked list, this algorithm isn't available because the nodes could be scattered anywhere in RAM. To find the last node, we have to follow the links from one node to the next. The more objects we have in our list, the more nodes we need to traverse, so the algorithm scales linearly, $O(n)$, with the input size.

The task is the same for both containers, but the algorithmic complexity can be different depending on how that container organizes its collection in memory.

Academic resources often disproportionately focus on abstract Big O analysis and underrepresent the importance of physical hardware, memory layout, and the "constant factors" that Big O ignores. In this abstract world, a linear solution is strictly superior to a quadratic solution, but that's not always true in the real world

When $n$ is small, the overhead of a complex algorithm can dwarf the actual work being done. You can implement a complex algorithm that should be highly efficient in theory, but if it doesn't consider the physical reality of the hardware, it can perform terribly in the real world.

Meanwhile, a beginner with no academic knowledge might store everything in arrays and solve every problem by looping over those arrays. Their approach can create highly performant systems by accident because they're taking full advantage of the caches through locality, and they're consistently accessing their data in predictable ways that the prefetcher can help with.

We can use Big O to prevent architectural disasters, but day-to-day, we use profiling to test and optimize the actual implementation.

In this lesson, we explored polynomial time complexity:

• Constant: The ideal - instant access, enabled by contiguous memory layouts and pointer arithmetic.
• Linear: The typical reality - we need to touch every item. The hardware loves this pattern if the data is stored contiguously, making it surprisingly fast.
• Quadratic: Where things begin to get dangerous - usually nested loops. Avoid this for large datasets.

We also learned that Big O is a model, not a law. For small data, a "bad" algorithm with good memory locality can beat a "good" algorithm with bad locality.

In the next lesson, we will look at logarithmic time - $O(\log n)$. We will see how we can exploit sorted data to discard half the workload with every single step, allowing us to search billions of items in nanoseconds.