Big-Oh Notation

When we discussed the complexity of a lookup operation on a List<T> in Chapter 5, we said it had runtime complexity O(n). What we meant to say informally is that, when you have a list of 1,000 items and are trying to find in it another item, then the worst-case running time of that operation is 1,000 iterations through the list—namely, if the item is not already in the list. Thus, we try to estimate the order of magnitude of the running time’s growth as the inputs become larger. When specified formally, however, the Big-Oh notation might appear slightly confusing:

Suppose that the function T(A;n) returns the number of computation steps required to execute the algorithm A on an input size of n elements, and let f(n) be a monotonic function from positive integers to positive integers. Then, T(A;n) is O(f(n)), if there exists a constant c such that for all n, T(A;n) ≤ cf(n).

In a nutshell, we can say that an algorithm’s runtime complexity is O(f(n)), if f(n) is an upper bound on the actual number of steps it takes to execute the algorithm on an input of size n. The bound does not have to be tight; for example, we can also say that List<T> lookup has runtime complexity O(n⁴). However, using such a loose upper bound is not helpful, because it fails to capture the fact that it is realistic to search a List<T> for an element even if it has 1,000,000 elements in it. If List<T> lookup had tight runtime complexity O(n⁴), it would be highly inefficient to perform lookups even on lists with several thousand elements.

Additionally, the bound might be tight for some inputs but not tight for others; for example, if we search the list for an item that happens to be its first element, the number of steps is clearly constant (one!) for all list sizes—this is why we mentioned worst-case running time in the preceding paragraphs.

Some examples of how this notation makes it easier to reason about running time and compare different algorithms include:

• If one algorithm has runtime complexity 2n ³ + 4 and another algorithm has runtime complexity ½n³-n², we can say that both algorithms have runtime complexity O(n³), so they are equivalent as far as Big-Oh complexity is concerned (try to find the constant c that works for each of these running times). It is easy to prove that we can omit all but the largest term when talking about Big-Oh complexity.
• If one algorithm that has runtime complexity n² and another algorithm has runtime complexity 100n + 5000, we can still assert that the first algorithm is slower on large inputs, because it has Big-Oh complexity O(n²), as opposed to O(n). Indeed, for n = 1,000, it is already the case that the first algorithm runs significantly slower than the second.

Similar to the definition of an upper bound on runtime complexity, there are also lower bounds (denoted by Ω(f(n)) and tight bounds (denoted by Θ(f(n)). They are less frequently used to discuss algorithm complexity, however, so we omit them here.

Turing Machines and Complexity Classes

It is common to refer to algorithms and problems as being “in P” or “in NP” or “NP-complete”. These refer to different complexity classes. The classification of problems into complexity classes helps computer scientists easily identify problems that have reasonable (tractable) solutions and reject or find simplifications for problems that do not.

A Turing machine (TM) is a theoretical computation device that models a machine operating on an infinite tape of symbols. The machine’s head can read or write one symbol at a time from the tape, and internally the machine can be in one of a finite number of states. The device’s operation is fully determined by a finite set of rules (an algorithm), such as “when in state Q and the symbol on the tape is ‘A’, write ‘a’ ” or “when in state P and the symbol on the tape is ‘a’, move the head to the right and switch to state S”. There are also two special states: the start state from which the machine begins operation and the end state. When the machine reaches the end state, it is common to say it loops forever or simply halts execution. Figure 9-1 shows an example of a Turing machine’s definition—the circles are states, and the arrows indicate state transitions in the syntax read;write;head_move_direction.

When discussing the complexity of algorithms on a Turing machine, there is no need to reason in vague “iterations”—a computation step of a TM is a single state transition (including a transition from a state to itself). For example, when the TM in Figure 9-1 starts with the input “AAAa#” on its tape, it performs exactly four computation steps. We can generalize this to say that, for an input of n ‘A’s followed by “a#”, the machine performs O(n) steps. (Indeed, for such an input of size n, the machine performs exactly n + 2 steps, so the definition of O(n) holds, for example, with the constant c = 3.)

Modeling real-world computation using a Turing machine is quite difficult—it makes for a good exercise in an undergraduate course on automata theory, but has no practical use. The amazing result is that every C# program (and, in fact, every algorithm that can be executed on a modern computer) can be translated—laboriously—to a Turing machine. Roughly speaking, if an algorithm written in C# has runtime complexity O( f (n)), then the same algorithm translated to a Turing machine has runtime complexity of O( f ²(n)). This has very useful implications on analyzing algorithm complexity: if a problem has an efficient algorithm for a Turing machine, then it has an efficient algorithm for a modern computer; if a problem does not have an efficient algorithm for a Turing machine, then it, typically, does not have an efficient algorithm for a modern computer.

Although we could call O(n²) algorithms efficient and any “slower” algorithms inefficient, complexity theory takes a slightly different stance. P is the set of all problems a Turing machine can solve in polynomial time—in other words, if A is a problem in P (with input of size n), then there exists a Turing machine that produces the desired result on its tape within polynomial time (i.e. within O(n ^k ) steps for some natural number k). In many subfields of complexity theory, problems in P are considered easy—and algorithms that run in polynomial time are considered efficient, even though k and, therefore, the running time can be very large for some algorithms.

All of the algorithms considered so far in this book are efficient if we embrace this definition. Still, some are “very” efficient and others less so, indicating that this separation is not sufficiently subtle. You might even ask whether there are any problems that are not in P, problems that do not have efficient solutions. The answer is a resounding yes—and, in fact, from a theoretical perspective, there are more problems that do not have efficient solutions than problems that do.

First, we consider a problem that a Turing machine cannot solve, regardless of efficiency. Then, we see there are problems a Turing machine can solve, but not in polynomial time. Finally, we turn to problems for which we do not know whether there is a Turing machine that can solve them in polynomial time, but strongly suspect that there is not.

public static bool DoesHaltOnInput(string programCode, string input) { . . . }

public static bool DoesHaltOnInput(Action< string > program, string input) { . . . }

public static void Helper(string programCode, string input) {
  bool doesHalt = DoesHaltOnInput(programCode, input);
  if (doesHalt) {
    while (true) {} //Enter an infinite loop
  }
}

Edit Distance

The edit distance between two strings is the number of character substitutions (deletions, insertions, and replacements) required to transform one string into the other. For example, the edit distance between “cat” and “hat” is 1 (replace ‘c’ with ‘h’), and the edit distance between “cat” and “groat” is 3 (insert ‘g’, insert ‘r’, replace ‘c’ with ‘o’). Efficiently finding the edit distance between two strings is important in many scenarios, such as error correction and spell checking with replacement suggestions.

The key to an efficient algorithm is breaking down the larger problem into smaller problems. For example, if we know that the edit distance between “cat” and “hat” is 1, then we also know that the edit distance between “cats” and “hat” is 2—we use the sub-problem already solved to devise the solution to the bigger problem. In practice, we wield this technique more carefully. Given two strings in array form, s[1. . .m] and t[1. . .n], the following hold:

• The edit distance between the empty string and t is n, and the edit distance between s and the empty string is m (by adding or removing all characters).
• If s[i] = t[j] and the edit distance between s[1. . .i-1] and t[1. . .j-1] is k, then we can keep the i-th character and the edit distance between s[1. . .i] and t[1. . .j] is k.
• If s[i] ≠ t[j], then the edit distance between s[1. . .i] and t[1. . .j] is the minimum of:

• The edit distance between s[1. . .i] and t[1. . .j-1], +1 to insert t[j];
• The edit distance between s[1. . .i-1] and t[1. . .j], +1 to delete s[i];
• The edit distance between s[1. . .i-1] and t[1. . .j-1], +1 to replace s[i] by t[j].

The following C# method finds the edit distance between two strings by constructing a table of edit distances for each of the substrings and then returning the edit distance in the ultimate cell in the table:

public static int EditDistance(string s, string t) {
  int m = s.Length, n = t.Length;
  int[,] ed = new int[m,n];
  for (int i = 0; i < m; ++i) {
    ed[i,0] = i + 1;
  }
  for (int j = 0; j < n; ++j) {
    ed[0,j] = j + 1;
  }
  for (int j = 1; j < n; ++j) {
    for (int i = 1; i < m; ++i) {
    if (s[i] == t[j]) {
    ed[i,j] = ed[i-1,j-1]; //No operation required
    } else { //Minimum between deletion, insertion, and substitution
    ed[i,j] = Math.Min(ed[i-1,j] + 1, Math.Min(ed[i,j-1] + 1, ed[i-1,j-1] + 1));
    }
    }
  }
  return ed[m-1,n-1];
}

The algorithm fills the edit distances table column-by-column, such that it never attempts to use data not yet calculated. Figure 9-2 illustrates the edit distances table constructed by the algorithm when run on the inputs “stutter” and “glutton”.

This algorithm uses O(mn) space and has running time complexity of O(mn). A comparable recursive solution that did not use memoization would have exponential running time complexity and fail to perform adequately even for medium-size strings.

All-Pairs-Shortest-Paths

The all-pairs-shortest-paths problem is to find the shortest distances between every two pairs of vertices in a graph. This can be useful for planning factory floors, estimating trip distances between cities, evaluating the required cost of fuel, and many other real-life scenarios. The authors encountered this problem in one of their consulting engagements. This was the problem description provided by the customer (see Sasha Goldshtein’s blog post at http://blog.sashag.net/archive/2010/12/16/all-pairs-shortest-paths-algorithm-in-real-life.aspx for the original story):

• We are implementing a service that manages a set of physical backup devices. There is a set of conveyor belts with intersections and robot arms that manipulate backup tapes across the room. The service gets requests, such as “transfer a fresh tape X from storage cabinet 13 to backup cabinet 89, and make sure to pass through formatting station C or D”.
• When the system starts, we calculate all shortest routes from every cabinet to every other cabinet, including special requests, such as going through a particular computer. This information is stored in a large hashtable indexed by route descriptions and with routes as values.
• System startup with 1,000 nodes and 250 intersections takes more than 30 minutes, and memory consumption reaches a peak of approximately 5GB. This is not acceptable.

First, we observe that the constraint “make sure to pass through formatting computer C or D” does not pose significant additional challenge. The shortest path from A to B going through C is the shortest path from A to C followed by the shortest path from C to B (the proof is almost a tautology).

The Floyd-Warshall algorithm finds the shortest paths between every pair of vertices in the graph and uses decomposition into smaller problems quite similar to what we have seen before. The recursive formula, this time, uses the same observation made above: the shortest path from A to B goes through some vertex V. Then to find the shortest path from A to B, we need to find first the shortest path from A to V and then the shortest path from V to B, and concatenate them together. Because we do not know what V is, we need to consider all possible intermediate vertices—one way to do so is by numbering them from 1 to n.

Now, the length of the shortest path (SP) from vertex i to vertex j using only the vertices 1,. . .,k is given by the following recursive formula, assuming there is no edge from i to j:

SP(i, j, k) = min { SP(i, j, k-1), SP(i, k, k-1) + SP(k, j, k-1) }

To see why, consider the vertex k. Either the shortest path from i to j uses this vertex or it does not. If the shortest path does not use the vertex k, then we do not have to use this vertex and can rely on the shortest path using only the vertices 1,. . .,k-1. If the shortest path uses the vertex k, then we have our decomposition—the shortest path can be sewn together from the shortest path from i to k (that uses only the vertices 1,. . .,k-1) and the shortest path from k to j (that uses only the vertices 1,. . .,k-1). See Figure 9–3 for an example.

To get rid of the recursive calls, we use memoization—this time we have a three-dimensional table to fill, and, after finding the values of SP for all pairs of vertices and all values of k, we have the solution to the all-pairs-shortest-paths problem.

We can further reduce the amount of storage space by noting that, for every pair of vertices i, j, we do not actually need all the values of k from 1 to n—we need only the minimum value obtained so far. This makes the table two-dimensional and the storage only O(n²). The running time complexity remains O(n³), which is quite incredible considering that we find the shortest path between every two vertices in the graph.

Finally, when filling the table, we need to record for each pair of vertices i, j the next vertex x to which we should proceed if we want to find the actual shortest path between the vertices. The translation of these ideas to C# code is quite easy, as is reconstructing the path based on this last observation:

static short[,] costs;
static short[,] next;
 
public static void AllPairsShortestPaths(short[] vertices, bool[,] hasEdge) {
  int N = vertices.Length;
  costs = new short[N, N];
  next = new short[N, N];
  for (short i = 0; i < N; ++i) {
    for (short j = 0; j < N; ++j) {
       costs[i, j] = hasEdge[i, j] ? (short)1 : short.MaxValue;
       if (costs[i, j] == 1)
          next[i, j] = −1; //Marker for direct edge
    }
  }
  for (short k = 0; k < N; ++k) {
    for (short i = 0; i < N; ++i) {
       for (short j = 0; j < N; ++j) {
          if (costs[i, k] + costs[k, j] < costs[i, j]) {
             costs[i, j] = (short)(costs[i, k] + costs[k, j]);
                next[i, j] = k;
          }
       }
    }
  }
}
public string GetPath(short src, short dst) {
    if (costs[src, dst] == short.MaxValue) return " < no path > ";
    short intermediate = next[src, dst];
    if (intermediate == −1)
       return "- > "; //Direct path
    return GetPath(src, intermediate) + intermediate + GetPath(intermediate, dst);
}

This simple algorithm improved the application performance dramatically. In a simulation with 300 nodes and an average fan-out of 3 edges from each node, constructing the full set of paths took 3 seconds and answering 100,000 queries about shortest paths took 120ms, with only 600KB of memory used.

Traveling Salesman

To perform a formal analysis, we need to formalize somewhat the traveling salesman problem referred to earlier. We are given a graph with a weight function w that assigns the graph’s edges positive values—you can think of this weight function as the distance between cities. The weight function satisfies the triangle inequality, which definitely holds if we keep to the analogy of traveling between cities on a Euclidean surface:

For all vertices x, y, z                w(x, y) + w(y, z) ≥ w(x, z)

The task, then, is to visit every vertex in the graph (every city on the salesman’s map) exactly once and return to the starting vertex (the company headquarters), making sure the sum of edge weights along this path is minimal. Let wOPT be this minimal weight. (The equivalent decision problem is NP-complete, as we have seen.)

The approximation algorithm proceeds as follows. First, construct a minimal spanning tree (MST) for the graph. Let wMST be the tree’s total weight. (A minimal spanning tree is a subgraph that touches every vertex, does not have cycles, and has the minimum total edge weight of all such trees.)

We can assert that wMST ≤ wOPT, because wOPT is the total weight of a cyclic path that visits every vertex; removing any edge from it produces a spanning tree, and wMST is the total weight of the minimum spanning tree. Armed with this observation, we produce a 2-approximation to wOPT using the minimum spanning tree as follows:

1. Construct an MST. There is a known O(n logn) greedy algorithm for this.
2. Traverse the MST from its root by visiting every node and returning to the root. The total weight of this path is 2wMST ≤ 2wOPT.
3. Fix the resulting path such that no vertex is visited more than once. If the situation in Figure 9-4 arises—the vertex y was visited more than once—then fix the path by removing the edges (x, y) and (y, z) and replacing them with the edge (x, z). This can only decrease the total weight of the path because of the triangle inequality.

   

   Figure 9-4 .  Instead of traversing Y twice, we can replace the path (X, Y, Z) with the path (X, Z)

The result is a 2-approximation algorithm, because the total weight of the path produced is still, at most, double the weight of the optimal path.

Maximum Cut

We are given a graph and need to find a cut—a grouping of its vertices into two disjoint sets—such that the number of edges crossing between the sets (crossing the cut) is maximal. This is known as the maximum cut problem, and solving it is quite useful for planning in many engineering fields.

We produce a very simple and intuitive algorithm that yields a 2-approximation:

1. Divide the vertices into two arbitrary disjoint sets, A and B.
2. Find a vertex v in A that has more neighbors in A than in B. If not found, halt.
3. Move v from A to B and go back to step 2.

First, let A be a subset of the vertices and v a vertex in A. We denote by deg_A(v) the number of vertices in A that v has an edge with (i.e. the number of its neighbors in A). Next, given two subsets A, B of the vertices, we denote by e(A, B) the number of edges between vertices in two different sets and by e(A) the number of edges between vertices in the set A.

When the algorithm terminates, for each v in A, it holds that deg_B(v) ≥ deg_A(v)—otherwise the algorithm would repeat step 2. Summing over all the vertices, we obtain that e(A, B) ≥ deg_B(v₁) + . . . + deg_B(v_k) ≥ deg_A(v₁) + . . . + deg_A(v_k) ≥ 2e(A), because every edge on the right hand side was counted twice. Similarly, e(A, B) ≥ 2e(B) and, therefore, 2e(A, B) ≥ 2e(A) + 2e(B). From this we obtain 2e(A, B) ≥ e(A, B) + e(A) + e(B), but the right hand side is the total number of edges in the graph. Therefore, the number of edges crossing the cut is at least one-half the total number of edges in the graph. The number of edges crossing the cut cannot be larger than the total number of edges in the graph, so we have a 2-approximation.

Finally, it is worth noting that the algorithm runs for a number of steps that is linear in the number of edges in the graph. Whenever step 2 repeats, the number of edges crossing the cut increases by at least 1, and it is bounded from above by the total number of edges in the graph, so the number of steps is also bounded from above by that number.

Probabilistic Maximum Cut

It turns out that a 2-approximation of the maximum cut problem can be obtained by randomly selecting the two disjoint sets (specifically, flipping a coin for each vertex to decide whether it goes into A or B). By probabilistic analysis, the expected number of edges crossing the cut is ½ the total number of edges.

To show that the expected number of edges crossing the cut is ½ the total number of edges, consider the probability that a specific edge (u, v) is crossing the cut. There are four alternatives with equal probability ¼: the edge is in A; the edge is in B; v is in A, and u is in B; and v is in B, and u is in A. Therefore, the probability the edge is crossing the cut is ½.

For an edge e, the expected value of the indicator variable X_e (that is equal to 1 when the edge is crossing the cut) is ½. By linearity of expectation, the expected number of edges in the cut is ½ the number of edges in the graph.

Note that we can no longer trust the results of a single round, but there are derandomization techniques (such as the method of conditional probabilities) that can make success very likely after a small constant number of rounds. We have to prove a bound on the probability that the number of edges crossing the cut is smaller than ½ the number of edges in the graph—there are several probabilistic tools, including Markov’s inequality, that can be used to this end. We do not, however, perform this exercise here.

Fermat Primality Test

Finding the prime numbers in a range is an operation we parallelized in Chapter 6, but we never got as far as looking for a considerably better algorithm for testing a single number for primality. This operation is important in applied cryptography. For example, the RSA asymmetric encryption algorithm used ubiquitously on the Internet relies on finding large primes to generate encryption keys.

A simple result from number theory known as Fermat’s little theorem states that, if p is prime, then for all numbers 1 ≤ a ≤ p, the number a ^p-1 has remainder 1 when divided by p (denoted a ^p-1 ≡ 1 (mod p)). We can use this idea to devise the following probabilistic primality test for a candidate n:

1. Pick a random number a in the interval [1, n], and see if the equality from Fermat’s little theorem holds (i.e. if a ^p-1 has remainder 1 when divided by p).
2. Reject the number as composite, if the equality does not hold.
3. Accept the number as prime or repeat step 1 until the desired confidence level is reached, if the equality holds.

For most composite numbers, a small number of iterations through this algorithm detects that it is composite and rejects it. All prime numbers pass the test for any number of repetitions, of course.

Unfortunately, there are infinitely many numbers (called Carmichael numbers) that are not prime but will pass the test for every value of a and any number of iterations. Although Carmichael numbers are quite rare, they are a sufficient cause of concern for improving the Fermat primality test with additional tests that can detect Carmichael numbers. The Miller-Rabin primality test is one example.

For composite numbers that are not Carmichael, the probability of selecting a number a for which the equality does not hold is more than ½. Thus, the probability of wrongly identifying a composite number as prime shrinks exponentially as the number of iterations increases: using a sufficient number of iterations can decrease arbitrarily the probability of accepting a composite number.

Variable Length Encoding

Suppose you have a collection of 50,000,000 positive integers to store on disk and you can guarantee that every integer will fit into a 32-bit int variable. A naïve solution would be to store 50,000,000 32-bit integers on disk, for a total of 200,000,000 bytes. We seek a better alternative that would use significantly less disk space. (One reason for compressing data on disk might be to load it more quickly into memory.)

Variable length encoding is a compression technique suitable for number sequences that contain many small values. Before we consider how it works, we need to guarantee that there will be many small values in the sequence—which currently does not seem to be the case. If the 50,000,000 integers are uniformly distributed in the range [0, 2³²], then more than 99% will not fit in 3 bytes and require a full 4 bytes of storage. However, we can sort the numbers prior to storing them on disk, and, instead of storing the numbers, store the gaps. This trick is called gap compression and likely makes the numbers much smaller, while still allowing us to reconstruct the original data.

For example, the series (38, 14, 77, 5, 90) is first sorted to (5, 14, 38, 77, 90) and then encoded using gap compression to (5, 9, 24, 39, 13). Note that the numbers are much smaller when using gap compression, and the average number of bits required to store them has gone down significantly. In our case, if the 50,000,000 integers were uniformly distributed in the range [0, 2³²], then many gaps would very likely fit in a single byte, which can contain values in the range [0, 256].

Next, we turn to the heart of variable byte length encoding, which is just one of a large number of methods in information theory that can compress data. The idea is to use the most significant bit of every byte to indicate whether it is the last byte that encodes a single integer or not. If the bit is off, go on to the next byte to reconstruct the number; if the bit is on, stop and use the bytes read so far to decode the value.

For example, the number 13 is encoded as 10001101—the high bit is on, so this byte contains an entire integer and the rest of it is simply the number 13 in binary. Next, the number 132 is encoded as 00000001`10000100. The first byte has its high bit off, so remember the seven bits 0000001, and the second byte has its high bit on, so append the seven bits 0000000 and obtain 10000100, which is the number 132 in binary. In this example, one of the numbers was stored using just 1 byte, and the other using 2 bytes. Storing the gaps obtained in the previous step using this technique is likely to compress the original data almost four-fold. (You can experiment with randomly generated integers to establish this result.)

Index Compression

To store an index of words that appear on web pages in an efficient way—which is the foundation of a crude search engine—we need to store, for each word, the page numbers (or URLs) in which it appears, compressing the data, while maintaining efficient access to it. In typical settings, the page numbers in which a word appears do not fit in main memory, but the dictionary of words just might.

Storing on disk the page numbers in which dictionary words appear is a task best left to variable length encoding—which we just considered. However, storing the dictionary itself is somewhat more complex. Ideally, the dictionary is a simple array of entries that contain the word itself and a disk offset to the page numbers in which the words appears. To enable efficient access to this data, it should be sorted—this guarantees O(logn) access times.

Suppose each entry is the in-memory representation of the following C# value type, and the entire dictionary is an array of them:

struct DictionaryEntry {
  public string Word;
  public ulong DiskOffset;
}
DictionaryEntry[] dictionary = . . .;

As Chapter 3 illustrates, an array of value types consists solely of the value type instances. However, each value type contains a reference to a string; for n entries, these references, along with the disk offsets, occupy 16n bytes on a 64-bit system. Additionally, the dictionary words themselves take up valuable space, and each dictionary word—stored as a separate string— has an extra 24 bytes of overhead (16 bytes of object overhead + 4 bytes to store the string length + 4 bytes to store the number of characters in the character buffer used internally by the string).

We can considerably decrease the amount of space required to store the dictionary entries by concatenating all dictionary words to a single long string and storing offsets into the string in the DictionaryEntry structure (see Figure 9-5). These concatenated dictionary strings are rarely longer than 2²⁴ bytes = 16MB, meaning the index field can be a 3-byte integer instead of an 8-byte memory address:

[StructLayout(LayoutKind.Sequential, Pack = 1, Size = 3)]
struct ThreeByteInteger {
  private byte a, b, c;
  public ThreeByteInteger() {}
  public ThreeByteInteger(uint integer) . . .
  public static implicit operator int(ThreeByteInteger tbi) . . .
}
struct DictionaryEntry {
  public ThreeByteInteger LongStringOffset;
  public ulong    DiskOffset;
}
class Dictionary {
  public DictionaryEntry[] Entries = . . .;
  public string    LongString;
}

The result is that we maintain binary search semantics over the array—because the entries have uniform size—but the amount of data stored is significantly smaller. We saved almost 24n bytes for the string objects in memory (there is now just one long string) and another 5n bytes for the string references replaced by offset pointers.