Topics: Data Structures and Algorithm, C++, Python

Theoretical Runtime Analysis of an Algorithm

Posted Dec. 2, 2024

Science is what we understand well enough to explain to a computer. Art is everything else we do.

Donald Knuth

Introduction

What is the Best Way to Compare Algorithms' Efficiency?

Given two algorithms that perform the same task, what is the best way to compare their performance? At first glance, one might consider measuring the runtime of the two algorithms. However, this is not a reliable metric, as runtime depends heavily on the hardware and can be highly inconsistent due to real-world conditions, even on the same machine. To address this problem, scientists have developed a more theoretical approach called the time complexity of an algorithm. This measure evaluates how an algorithm's performance scales as the size of the input increases.

If $n$ is the number of input, then for a given algorithm, there exists a function $f(n)$ that measures the worst-case runtime of the algorithm as $n$ varies. The runtime of an algorithm generally follows a specific trend, such as constant, logarithmic, or linear. However, as noted, the runtime is significantly influenced by hardware and physical conditions. Therefore, these functions are often expressed with additional constant factors, such as:

\begin{equation}f(n) = C_1n + C_0,\end{equation}

where $C_1$ and $C_0$ are factors that depends on outside conditions. This expression is quite inconvenient, as we don't usually know what these constant factors are, so the general rule of thumb to express the worst-case runtime of an algorithm is through the big-O notation. For example, if $f(n) = C_1n + C_0$, then it can be said that

\begin{equation}f(n) \in O(n).\end{equation}

There are many categories of such functions $f(n)$, and the most important functions used in algorithmic analysis are the constant function, $f(n)=c$, the logarithm function $f(n) = \log_b(n)$, the linear function $f(n) = n$, $f(n) = n\log(n)$, the quadratic function $f(n) = n^2$, other polynomial functions $f(n) = n^d$, the exponential functions $f(n) = a^n$, and the factorial function $f(n) = n!$.

The Big O, Big Omega, Big Theta, and Their Properties

Merge sort splits the input array into halves, recursively sorts both halves, then merges two sorted arrays in linear time. Let $T(n)$ be the time to sort $n$ items. The recurrence is

\begin{equation}T(n) = 2\,T\!\left(\tfrac{n}{2}\right) + \Theta(n).\end{equation}

Here $a=2$, $b=2$, and $f(n)=\Theta(n)$ matches Case 2 of the Master Theorem with $k=0,\;\log_b a=1$, yielding $T(n) \in \Theta(n\,\log n)$. The merge step uses linear extra space, so space complexity is $\Theta(n)$.

The Big O Notation

Let $f$ and $g$ be real-valued and not necessarily continuous functions. We say that $f$ is the big O of $g$, written

\begin{equation}f(n) = O(g(n)),\quad n \to \infty,\end{equation}

if there exists some value $n_0$ such that

\begin{equation}|f(n)| \le M|g(n)|,\quad \forall n \ge n_0.\end{equation}

for some constant $M > 0$.

For example, $f(n) = 3n \in O(n)$ because $|3n| \le M|n|$ for $n \ge 0$, and $M$ can be any number greater than or equal to 3. Similarly, $8n + 5 \in O(n)$ because choosing $M = 9$ and $n_0 = 5$ gives $8n + 5 \le 9n$ for all $n \ge 5$.

Binary search on a sorted array halves the search interval each iteration. The recurrence is

\begin{equation}T(n) = T\!\left(\tfrac{n}{2}\right) + \Theta(1).\end{equation}

With $a=1$, $b=2$, $f(n)=\Theta(1)$, we have $\log_b a = 0$ and Case 2 gives $T(n) \in \Theta(\log n)$. Iterative binary search uses $\Theta(1)$ extra space; the naive recursive form uses $\Theta(\log n)$ stack space.

The Big Omega Notation

Big Omega provides a lower bound on the growth of a function. We say that $f$ is the big Omega of $g$, written

\begin{equation}f(n) = \Omega(g(n)),\quad n \to \infty,\end{equation}

if there exists some value $n_0$ such that

\begin{equation}|f(n)| \ge M|g(n)|,\quad \forall n \ge n_0,\end{equation}

for some constant $M > 0$.

For example, $5n \in \Omega(n)$ since $|5n| \ge M|n|$ with $M = 5$ for all $n \ge 0$. Likewise, $2n^2 + 7n \in \Omega(n^2)$ because for large enough $n$, the quadratic term dominates.

Using Kahn's algorithm (indegree + queue) or DFS, each vertex is enqueued/visited a constant number of times and each edge is examined once. For a DAG with $V$ vertices and $E$ edges, the runtime is $\Theta(V+E)$; space is $\Theta(V)$ for the queue/stack and $\Theta(V+E)$ for adjacency lists.

The Big Theta Notation

Big Theta describes a tight bound on the growth of a function. We say that $f$ is the big Theta of $g$, written

\begin{equation}f(n) = \Theta(g(n)),\quad n \to \infty,\end{equation}

if there exist constants $M_1, M_2 > 0$ and a value $n_0$ such that

\begin{equation}M_1|g(n)| \le |f(n)| \le M_2|g(n)|,\quad \forall n \ge n_0.\end{equation}

For example, $7n + 4 \in \Theta(n)$ because the linear term dominates and both an upper bound and a lower bound proportional to $n$ can be found. Similarly, $3n^3 - 2n \in \Theta(n^3)$ because the cubic term determines the growth rate.

With adjacency lists and a binary heap priority queue:

Extract-min occurs $V$ times at $\Theta(\log V)$ each.
Decrease-key (relaxation) occurs up to $E$ times at $\Theta(\log V)$ each.
Scanning adjacency lists costs $\Theta(E)$ overall.

Total time $\Theta\big((V+E)\log V\big)$; with an array as the queue it is $\Theta(V^2+E)$; with a Fibonacci heap it becomes $\Theta(E+V\log V)$.

Useful Properties

Ignore constants: $c\,f(n) \in \Theta(f(n))$ for any constant $c>0$.
Base of logs: $\log_a n \in \Theta(\log_b n)$ for any fixed bases $a,b>1$.
Sum dominated by max: $f(n)+g(n) \in \Theta(\max\{f(n),g(n)\})$ if one eventually dominates.
Products: If $f\in O(g)$ and $h\in O(k)$, then $fh \in O(gk)$.
Polynomial vs. exponential: For any constant $d>0$ and any $a>1$, $n^d \in o(a^n)$.
Transitivity: If $f\in O(g)$ and $g\in O(h)$ then $f\in O(h)$ (similarly for $\Omega$).

The Master Theorem

Many divide-and-conquer algorithms lead to recurrences of the form

\begin{equation}T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n), \quad a \ge 1,\; b>1,\end{equation}

where $a$ subproblems of size $n/b$ are solved and $f(n)$ accounts for splitting/merging work. The Master Theorem gives asymptotic solutions:

Case 1: If $f(n) \in O\big(n^{\log_b a - \varepsilon}\big)$ for some $\varepsilon>0$, then $T(n) \in \Theta\big(n^{\log_b a}\big)$.
Case 2: If $f(n) = \Theta\big(n^{\log_b a}\,\log^k n\big)$ for some $k \ge 0$, then $T(n) \in \Theta\big(n^{\log_b a}\,\log^{k+1} n\big)$.
Case 3: If $f(n) \in \Omega\big(n^{\log_b a + \varepsilon}\big)$ for some $\varepsilon>0$ and $a\,f(n/b) \le c\,f(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n) \in \Theta\big(f(n)\big)$.

Runtime Analysis of an Algorithm

Quoting a running time is not the same as proving one. A complete analysis has four parts:

a machine model that says what a single step costs
a precise statement of the algorithm, so that "the number of steps" is a well-defined quantity
an upper bound, exhibiting explicit constants $M$ and $n_0$ as demanded by the definition of $O$
a matching lower bound, exhibiting an infinite family of inputs on which the algorithm really is that slow; without it, one has only proved $O$, never $\Theta$.

The four analyzes below are carried out in that style: every claim is stated as a lemma or theorem and proved, and no constant is hidden that could not be written down.

Preliminaries: The Cost Model

The random-access machine (RAM) has an unbounded sequence of memory cells, each holding one word of $w = \Theta(\log n)$ bits. The following are primitive operations and each costs one unit of time: reading or writing the cell at a computed address; addition, subtraction, multiplication, integer division, and comparison of two words; and one branch or one assignment. The running time T_{\mathcal{A}}(x) of an algorithm \mathcal{A} on an input $x$ is the number of primitive operations it executes before halting.

Fix a size measure |\cdot| on inputs. The worst-case running time of \mathcal{A} is

\begin{equation}T(n) \;=\; \max\{\, T_{\mathcal{A}}(x) \;:\; |x| = n \,\}.\end{equation}

To prove $T(n) \in \Theta(g(n))$ one must therefore produce constants M_1, M_2 > 0 and a threshold $n_0$ with M_1 g(n) \le T(n) \le M_2 g(n) for all n \ge n_0: the upper bound must hold for every input of size $n$, while the lower bound need only be witnessed by one input of each size.

Two elementary facts are used repeatedly and are worth isolating. The first is the counting identity that makes graph algorithms come out linear in $V+E$; the second is the reason a "halving" argument survives the floors and ceilings that real code introduces.

Lemma 1 (Handshake lemma for digraphs). Let $G=(V,E)$ be a directed graph, and for a vertex $v$ let \deg^+(v) and \deg^-(v) denote its out-degree and in-degree. Then

\begin{equation}\sum_{v \in V} \deg^+(v) \;=\; \sum_{v \in V} \deg^-(v) \;=\; |E|.\end{equation}

Count the set of pairs P = \{(v,e) \in V \times E : v \text{ is the tail of } e\} in two ways. Grouping by the first coordinate gives |P| = \sum_{v} \deg^+(v), since the pairs with first coordinate $v$ are exactly the edges leaving $v$. Grouping by the second coordinate gives |P| = |E|, since every edge has exactly one tail and therefore appears in exactly one pair. The two counts of the same finite set agree. Repeating the argument with "tail" replaced by "head" gives the second equality.

Lemma 2 (Nested floors and ceilings). For every real $x$ and all positive integers $a,b$,

\begin{equation}\left\lfloor \frac{\lfloor x/a \rfloor}{b} \right\rfloor = \left\lfloor \frac{x}{ab} \right\rfloor, \qquad \left\lceil \frac{\lceil x/a \rceil}{b} \right\rceil = \left\lceil \frac{x}{ab} \right\rceil.\end{equation}

For the first identity, let m = \lfloor \lfloor x/a \rfloor / b \rfloor. Then $m$ is the largest integer with mb \le \lfloor x/a \rfloor. Since $mb$ is an integer, mb \le \lfloor x/a \rfloor \iff mb \le x/a \iff mab \le x, where the middle equivalence is the defining property of the floor (an integer is $\le \lfloor y \rfloor$ if and only if it is $\le y$). Hence $m$ is the largest integer with $m \le x/(ab)$, i.e. m = \lfloor x/(ab) \rfloor. The ceiling identity follows by the same argument with all inequalities reversed, using that an integer is \ge \lceil y \rceil if and only if it is $\ge y$.

Example 1: Binary Search

Binary search looks for a key $x$ in a sorted array $A[1 \ldots n]$. The claim "it halves the interval, therefore it is logarithmic" is the right intuition but not a proof: the interval is not halved, it is reduced to \lfloor (s-1)/2 \rfloor or \lceil (s-1)/2 \rceil, and one has to check that this still forces $\Theta(\log n)$ from both sides.

Binary-Search(A, n, x) // A[1..n] sorted nondecreasingly
lo <- 1;  hi <- n
while lo <= hi do
  mid <- floor((lo + hi) / 2)
  if   A[mid] = x then return mid
  elif A[mid] < x then lo <- mid + 1
  else                 hi <- mid - 1
return not-found

Write s_k = \mathit{hi} - \mathit{lo} + 1 for the number of candidate positions still under consideration after $k$ completed iterations, so that s_0 = n, and observe that the loop guard \mathit{lo} \le \mathit{hi} is exactly the condition s_k \ge 1.

Lemma 6 (One iteration). Suppose iteration $k+1$ is entered (so s_k \ge 1) and does not return. Then

\begin{equation}s_{k+1} \in \left\{ \left\lfloor \frac{s_k - 1}{2} \right\rfloor,\; \left\lceil \frac{s_k - 1}{2} \right\rceil \right\}, \qquad\text{hence}\qquad \frac{s_k - 2}{2} \;\le\; s_{k+1} \;\le\; \frac{s_k}{2}.\end{equation}

Put $s = s_k$ and write \mathit{mid} = \lfloor (\mathit{lo}+\mathit{hi})/2 \rfloor. If the algorithm takes the branch \mathit{lo} \leftarrow \mathit{mid}+1, the new count is

\begin{equation}\mathit{hi} - \mathit{mid} = \mathit{hi} - \left\lfloor \frac{\mathit{lo}+\mathit{hi}}{2} \right\rfloor = \left\lceil \frac{\mathit{hi}-\mathit{lo}}{2} \right\rceil = \left\lceil \frac{s-1}{2} \right\rceil,\end{equation}

and if it takes the branch \mathit{hi} \leftarrow \mathit{mid}-1 it is

\begin{equation}\mathit{mid} - \mathit{lo} = \left\lfloor \frac{\mathit{lo}+\mathit{hi}}{2} \right\rfloor - \mathit{lo} = \left\lfloor \frac{\mathit{hi}-\mathit{lo}}{2} \right\rfloor = \left\lfloor \frac{s-1}{2} \right\rfloor.\end{equation}

For the numeric bounds: \lceil (s-1)/2 \rceil \le s/2 holds because for even $s$ the left side is $s/2$ exactly, and for odd $s$ it equals $(s-1)/2 < s/2$; and \lfloor (s-1)/2 \rfloor \ge (s-2)/2 because \lfloor y \rfloor > y-1.

The worst-case running time of Binary-Search satisfies T(n) \in \Theta(\log n). More precisely, the loop executes at most \lfloor \log_2 n \rfloor + 1 iterations on every input, and at least \log_2 n - 2 iterations on the input where $x$ is smaller than every element of $A$.

Upper bound. We claim s_k \le n/2^k for every $k$ at which the loop is still running. This is an induction: s_0 = n, and if s_k \le n/2^k then by Lemma 6 s_{k+1} \le s_k/2 \le n/2^{k+1}. Now iteration $k+1$ is entered only if s_k \ge 1, which forces n/2^k \ge 1, i.e. k \le \log_2 n. The iterations are therefore indexed by k = 0, 1, \ldots, \lfloor \log_2 n \rfloor, at most \lfloor \log_2 n \rfloor + 1 of them. Each iteration executes a fixed number of primitive operations (one addition, one halving, one array read and at most two comparisons and one assignment), say at most $c$; adding the constant $d$ for initialization and the final return,

\begin{equation}T(n) \;\le\; c\left( \lfloor \log_2 n \rfloor + 1 \right) + d \;\le\; 2c \log_2 n \quad\text{for } n \ge 2^{(c+d)/c},\end{equation}

so T(n) \in O(\log n).

Lower bound. Take the input in which $x$ is strictly smaller than every $A[i]$. Then no comparison can report equality, the algorithm never returns early, and every iteration takes the branch \mathit{hi} \leftarrow \mathit{mid}-1, so by Lemma 6 s_{k+1} = \lfloor (s_k-1)/2 \rfloor \ge (s_k-2)/2. We claim s_k \ge n/2^k - 2 for every $k$ reached. Indeed s_0 = n \ge n - 2, and if the claim holds at $k$ then

\begin{equation}s_{k+1} \;\ge\; \frac{s_k - 2}{2} \;\ge\; \frac{n/2^k - 4}{2} \;=\; \frac{n}{2^{k+1}} - 2.\end{equation}

Consequently s_k \ge 1, and hence another iteration runs, whenever n/2^k \ge 3, that is whenever k \le \log_2 n - \log_2 3. The number of iterations on this input is therefore at least \log_2 n - \log_2 3 \ge \log_2 n - 2, and since each iteration costs at least one primitive operation, T(n) \ge \log_2 n - 2 \ge \tfrac12 \log_2 n for $n \ge 16$. With the upper bound this gives T(n) \in \Theta(\log n).

Solving the recurrence gives the same answer with less information: the recursive form obeys T(n) = T(\lfloor n/2 \rfloor) + \Theta(1), which is the Master Theorem with $a=1$, $b=2$, \log_b a = 0 and f(n) = \Theta(1) = \Theta(n^0 \log^0 n): Case 2 with $k=0$, giving T(n) \in \Theta(\log n). Unrolling by hand is just as quick: T(n) = T(n/2^k) + \Theta(k) and the recursion bottoms out at k = \Theta(\log n).

Optimality. No comparison-based search can do better, and the proof is a counting argument rather than an analysis of any particular algorithm.

Lemma 7 (Leaves of a binary tree). A binary tree of height $h$ has at most 2^h leaves.

Induction on $h$. A tree of height $0$ is a single node, which is one leaf, and 2^0 = 1. A tree of height $h \ge 1$ has a root with at most two subtrees, each of height at most $h-1$; every leaf of the tree is a leaf of one of the subtrees, so the leaf count is at most 2 \cdot 2^{h-1} = 2^h.

Let \mathcal{A} be any deterministic algorithm that, given a sorted array of $n$ distinct keys and a key $x$ not present in the array, determines the position at which $x$ would have to be inserted, using only comparisons between $x$ and array entries. Then \mathcal{A} performs at least \lceil \log_2 (n+1) \rceil comparisons on some input.

Because $x$ is absent, every comparison $x$ versus $A[i]$ has exactly two possible outcomes, so the execution of \mathcal{A} on the family of such inputs is described by a binary tree: each internal node is the comparison the algorithm performs next (determined by the outcomes so far, since \mathcal{A} is deterministic), its two children are the two outcomes, and each leaf carries the answer output there. There are $n+1$ possible answers, one for each gap between consecutive elements including the two ends, and every one of them occurs for some input. Two different answers cannot share a leaf, since all inputs reaching a leaf receive the same output; hence the tree has at least $n+1$ leaves, and by Lemma 7 its height $h$ satisfies 2^h \ge n+1, i.e. h \ge \lceil \log_2(n+1) \rceil. A root-to-leaf path of that length is an input on which \mathcal{A} makes that many comparisons.

Binary search performs at most \lfloor \log_2 n \rfloor + 1 comparisons, so it is optimal up to an additive constant.

Space. The iterative version keeps only \mathit{lo}, \mathit{hi} and \mathit{mid}, so its auxiliary space is $\Theta(1)$. The recursive version pushes one $O(1)$-sized frame per iteration and, by the theorem above, makes at most \lfloor \log_2 n \rfloor + 1 of them before returning, so its stack usage is $\Theta(\log n)$ in the worst case, unless the compiler eliminates the tail call, in which case it is again $\Theta(1)$.

Example 2: Topological Sort

Let $G = (V,E)$ be a directed graph given by adjacency lists, and write $V$ and $E$ for both the sets and their cardinalities, as is customary. A topological order is a linear order of the vertices in which every edge points forward. The statement "each vertex and each edge is visited a constant number of times" is the whole content of the $\Theta(V+E)$ bound, so it is precisely that statement which has to be proved, and it is not obvious, because a vertex could in principle be pushed onto the queue once per incoming edge.

Kahn(G)
  for each v in V do indeg[v] <- 0                      // pass 1
  for each u in V do                                    // pass 2
      for each v in Adj[u] do indeg[v] <- indeg[v] + 1
  S <- empty queue                                      // pass 3
  for each v in V do
      if indeg[v] = 0 then Enqueue(S, v)
  L <- empty list;  count <- 0
  while S is not empty do                               // main loop
      u <- Dequeue(S);  append u to L;  count <- count + 1
      for each v in Adj[u] do
          indeg[v] <- indeg[v] - 1
          if indeg[v] = 0 then Enqueue(S, v)
  if count < |V| then report "G has a cycle" else return L

Lemma 8 (Each vertex is enqueued at most once). Over the whole execution, Enqueue(S, v) is executed at most once for each vertex $v$.

After pass 2 the counter indeg[v] holds \deg^-(v), and from that moment on it is only ever decremented; it is therefore a strictly decreasing function of time on the (finite) set of instants at which it changes. A strictly decreasing integer-valued function takes the value $0$ at most once, so there is at most one instant $t_v$ at which \mathit{indeg}[v] = 0 holds and can be observed. Every enqueue of $v$ is guarded by a test \mathit{indeg}[v] = 0 (in pass 3 if \deg^-(v) = 0 already, and in the main loop immediately after a decrement); hence every enqueue of $v$ happens at $t_v$, and the tests in question occur at most once each at that instant.

Lemma 9 (Each adjacency list is scanned at most once). The inner loop of the main loop scans \mathit{Adj}[u] at most once for each $u$; consequently the main loop performs at most \sum_{u \in V} \deg^+(u) = E decrements in total.

The scan of \mathit{Adj}[u] is executed only in the iteration of the main loop that dequeues $u$. Since the queue is a set of enqueued items and each dequeue removes one item, the number of dequeues of $u$ is at most the number of enqueues of $u$, which is at most one by Lemma 8. The count of decrements follows from the handshake identity of Lemma 1.

Lemma 10 (Termination with all vertices, on a DAG). If $G$ is acyclic, then at termination $count = |V|$; every vertex is enqueued and dequeued exactly once. If $G$ has a cycle, then \mathit{count} < |V|, so the final test is a correct acyclicity test.

Suppose $G$ is acyclic but some vertices are never enqueued; let $W$ be the (non-empty) set of those vertices. The main loop runs until $S$ is empty, so every enqueued vertex is eventually dequeued; hence the dequeued vertices are exactly V \setminus W. Fix v \in W. Its counter is tested for $0$ after every decrement, and $v$ was never enqueued, so its counter was never $0$; at termination it equals

\begin{equation}\mathit{indeg}[v] \;=\; \deg^-(v) \;-\; \#\{\, u : (u,v) \in E \text{ and } u \text{ was dequeued} \,\} \;>\; 0,\end{equation}

which means $v$ has an in-neighbor $u$ that was never dequeued, i.e. u \in W. So every vertex of $W$ has an in-neighbor inside $W$. Starting from any v_0 \in W and repeatedly stepping to such an in-neighbor produces an infinite walk v_0 \leftarrow v_1 \leftarrow v_2 \leftarrow \cdots inside the finite set $W$; by the pigeonhole principle two of the v_i coincide, say v_i = v_j with i < j, and then v_j \to v_{j-1} \to \cdots \to v_i is a directed cycle, contradicting acyclicity. Hence $W$ is empty. Conversely, if $G$ contains a cycle $C$, no vertex of $C$ can ever be dequeued: the first vertex of $C$ to be dequeued would have had its counter reach $0$, yet its predecessor on $C$ had not been dequeued at that time and so had not contributed its decrement, and the counter never dips below the number of undecremented in-edges. Therefore \mathit{count} \le |V| - |C| < |V|.

Kahn runs in time $\Theta(V+E)$ on every input, in the adjacency-list representation.

Upper bound. Pass 1 and pass 3 execute $O(1)$ work per vertex, so $O(V)$ each. Pass 2 executes $O(1)$ work per adjacency entry, so by Lemma 1 it costs O\!\left(V + \sum_u \deg^+(u)\right) = O(V+E), the $V$ accounting for the per-vertex loop overhead even at vertices with empty lists. In the main loop, the work of the iteration that dequeues $u$ is O(1) + O(\deg^+(u)): a dequeue, an append, an increment, and one pass over \mathit{Adj}[u] doing $O(1)$ work per entry. Each vertex is dequeued at most once (Lemma 9), so summing over the dequeued vertices and applying Lemma 1 again bounds the main loop by

\begin{equation}\sum_{u \in V} \left( c_1 + c_2 \deg^+(u) \right) \;=\; c_1 V + c_2 E.\end{equation}

Adding the passes gives T \le M(V+E) for a constant $M$.

Lower bound. Passes 1–3 are executed unconditionally and already touch all $V$ vertices and all $E$ adjacency entries, at a cost of at least one primitive operation each, so T \ge V + E on every input. Hence T \in \Theta(V+E).

Remark (why no algorithm can do better). The theorem is a statement about this algorithm; that the problem needs $\Omega(V+E)$ is a separate, adversary-style argument. The $\Omega(V)$ half is immediate, since the output has $V$ entries. For the $\Omega(E)$ half, fix $q$ and let G_0 be the graph on a_1,\ldots,a_q,\, b_1,\ldots,b_q with all q^2 edges (a_i, b_j); it is acyclic, as no edge leaves a $b$. For each edge $e$, let G_e be the same graph with $e$ reversed; G_e is acyclic too, because a cycle would have to leave b_j along the single reversed edge and return to it, and the only edges into b_j come from the $a$'s, which have no other way back. Now suppose a deterministic algorithm halts on G_0 without ever inspecting the adjacency entry for $e = (a_i, b_j)$. Run it on G_e: every value it reads is identical, so it produces the same order. That order places a_i before b_j or the other way round, and is therefore wrong on one of the two acyclic inputs. Hence on G_0 the algorithm inspects all q^2 entries, which is $\Omega(E)$ with $V = 2q$; padding with isolated vertices and thinning the bipartite core tunes $V$ and $E$ independently. Kahn's algorithm is therefore optimal to within a constant factor.

The DFS formulation. The alternative algorithm runs a depth-first search over all vertices and prepends each vertex to a list when it is finished. Its cost is $\Theta(V+E)$ for the same reason in a different disguise: DFS-Visit(u) is called only when $u$ is white and colors it gray on entry, and colors are never reset, so it is called at most once per vertex; it then scans \mathit{Adj}[u] exactly once, doing $O(1)$ work per entry, and the outer loop contributes $O(V)$. Summing with Lemma 1 gives $O(V+E)$, and the outer loop's unconditional pass over $V$ plus the scan of every adjacency list gives $\Omega(V+E)$. The order produced is correct because for every edge $(u,v)$ one has $f(v) < f(u)$ for the finishing times: when the edge is explored $u$ is gray, and $v$ is then either white, in which case it becomes a descendant of $u$ and finishes first, or black, so it has already finished, or gray, which would make $(u,v)$ a back edge and produce a cycle, impossible in a DAG.

Space. Both formulations use $\Theta(V)$ auxiliary space (the counters and queue for Kahn, the colors and the recursion stack of depth at most $V$ for DFS) on top of the $\Theta(V+E)$ occupied by the input itself.

Example 3: Dijkstra's Algorithm

Dijkstra's algorithm computes single-source shortest paths in a directed graph with non-negative edge weights w : E \to \mathbb{R}_{\ge 0}. Its running time is not a property of the algorithm alone: it is the number of priority-queue operations, which depends only on the graph, multiplied by the cost of those operations, which depends only on the queue. Separating the two is the whole analysis, and it is what makes the array, binary-heap and Fibonacci-heap variants three corollaries of one theorem instead of three separate arguments.

Dijkstra(G, w, s)
  for each v in V do d[v] <- infinity;  parent[v] <- nil;  done[v] <- false
  d[s] <- 0
  Q <- priority queue containing every v in V, keyed by d[v]
  while Q is not empty do
      u <- Extract-Min(Q)
      done[u] <- true
      for each v in Adj[u] do                          // relax edge (u,v)
          if not done[v] and d[u] + w(u,v) < d[v] then
              d[v] <- d[u] + w(u,v)
              parent[v] <- u
              Decrease-Key(Q, v, d[v])

Lemma 11 (Operation counts). On a graph with $V$ vertices and $E$ edges, one execution of Dijkstra performs exactly $V$ Extract-Min operations, at most $E$ Decrease-Key operations, one queue construction of $V$ elements, and $\Theta(V+E)$ additional primitive operations outside the queue.

No element is ever inserted after the queue is built, and each iteration of the main loop removes exactly one element, so the loop runs exactly $V$ times and performs exactly $V$ extractions; in particular every vertex is extracted exactly once. The scan of \mathit{Adj}[u] occurs only in the iteration that extracts $u$, hence at most once per vertex, so each edge $(u,v)$ is relaxed at most once and each relaxation issues at most one Decrease-Key. By Lemma 1 the number of relaxations is \sum_u \deg^+(u) = E, bounding the decrease-keys by $E$. Outside the queue, the initialization is $\Theta(V)$, the main loop's per-iteration bookkeeping is $O(1)$, and the adjacency scans cost $\Theta(1)$ per entry, $\Theta(E)$ in total; the sum is $\Theta(V+E)$.

Note what this proof did not use: non-negativity of the weights. The counting holds because of the done flag, which lets a vertex be extracted only once. Non-negativity is what makes that safe: it is needed for correctness, to guarantee that d[u] is already final when $u$ is extracted. A "lazy" implementation that reinserts vertices instead of decreasing keys can, on graphs with negative edges, perform exponentially many extractions. Correctness and the running-time bound are entangled here, not independent.

Lemma 12 (Binary heap operations). A binary min-heap holding $h$ elements in a complete binary tree has height \lfloor \log_2 h \rfloor, and Insert, Extract-Min and Decrease-Key each run in O(\log h) time; building a heap of $h$ elements costs $\Theta(h)$.

A complete binary tree of height $\eta$ has all levels 0, \ldots, \eta-1 full and level $\eta$ non-empty, so its size $h$ satisfies 2^{\eta} \le h \le 2^{\eta+1} - 1, whence \eta \le \log_2 h < \eta + 1 and \eta = \lfloor \log_2 h \rfloor. Sift-Up compares an element with its parent and, if they are out of order, swaps and repeats one level higher; each iteration strictly decreases the element's depth, so there are at most $\eta$ iterations of $O(1)$ work each. Sift-Down likewise strictly increases the depth by one per iteration. Since Insert is an append followed by a Sift-Up, Decrease-Key is a key update followed by a Sift-Up (the heap property can only be violated upwards), and Extract-Min moves the last element to the root and calls Sift-Down, all three cost O(\eta) = O(\log h). For the construction, sifting down every node from the bottom up costs at most

\begin{equation}\sum_{\ell=0}^{\eta} \left\lceil \frac{h}{2^{\ell+1}} \right\rceil O(\eta - \ell) \;=\; O\!\left( h \sum_{i=0}^{\infty} \frac{i}{2^{i}} \right) \;=\; O(2h) \;=\; O(h),\end{equation}

using that level $\ell$ holds at most \lceil h/2^{\ell+1} \rceil nodes whose sift-down travels at most \eta - \ell levels, and that \sum_{i \ge 0} i/2^i = 2. It is also $\Omega(h)$ since every element is touched.

With adjacency lists, Dijkstra runs in time

\begin{equation}T \;=\; \Theta(V+E) \;+\; V \cdot C_{\text{ext}} \;+\; O(E) \cdot C_{\text{dec}} \;+\; C_{\text{build}},\end{equation}

where C_{\text{ext}}, C_{\text{dec}}, C_{\text{build}} are the costs of an extract-min, a decrease-key and building the queue. In particular:

binary heap: T \in O\big((V+E)\log V\big);
unsorted array: T \in \Theta(V^2 + E) = \Theta(V^2);
Fibonacci heap: T \in O\big(E + V \log V\big).

The displayed identity is Lemma 11 together with the observation that the algorithm's work splits into queue operations and everything else, and that the costs are additive. The three cases are then substitutions.

Binary heap. The queue never holds more than $V$ elements, so by Lemma 12 C_{\text{ext}}, C_{\text{dec}} \in O(\log V) and C_{\text{build}} = \Theta(V). Substituting,

\begin{equation}T \;\in\; \Theta(V+E) + O(V \log V) + O(E \log V) + \Theta(V) \;=\; O\big((V+E)\log V\big).\end{equation}

If every vertex is reachable from $s$ then E \ge V-1 and this simplifies to O(E \log V).

Unsorted array. Take $Q$ to be an array of $V$ keys. Building it is $\Theta(V)$; an extract-min is a linear scan, C_{\text{ext}} = \Theta(V); a decrease-key is a single write, C_{\text{dec}} = \Theta(1). Hence T = \Theta(V+E) + V \cdot \Theta(V) + O(E) = \Theta(V^2+E), and since E \le V^2 this is \Theta(V^2). Unlike the heap bound, this one is a genuine $\Theta$: the $V$ linear scans are performed unconditionally.

Fibonacci heap. Fredman and Tarjan's structure supports insert and decrease-key in $O(1)$ amortized time and extract-min in O(\log h) amortized time, meaning that any sequence of $\alpha$ inserts, $\beta$ decrease-keys and $\gamma$ extract-mins on a heap of size at most $h$ costs O(\alpha + \beta + \gamma \log h) in total, even though an individual operation may cost more. With \alpha = V, \beta \le E, \gamma = V and $h \le V$, the queue's total contribution is O(V + E + V \log V), and adding the $\Theta(V+E)$ of Lemma 11 gives O(E + V\log V).

Why $O$ and not $\Theta$ for the heap variant. The bound \Theta((V+E)\log V) is quoted so often that it is worth saying exactly why it is an abuse of notation. Lemma 11 bounds the number of decrease-keys by $E$, but on many inputs almost none of them fire: if the edges are scanned in an order that never improves a tentative distance, the cost is \Theta(V \log V + E), which is smaller. And an individual heap operation costs \Theta(\log V) only in the worst case; a sift-up that stops immediately costs $O(1)$. So $O$ is the correct symbol for a statement about all inputs, and $\Theta$ is correct only for the worst case over a family of inputs that actually forces the work.

A matching lower bound. Something can still be proved from below, and it explains why the Fibonacci-heap bound is the end of the road for this approach. Let $G$ be the star with edges (s, v_i) of weights w_1, \ldots, w_{V-1}. Dijkstra extracts the vertices in non-decreasing order of distance, i.e. it outputs the w_i in sorted order. If the priority queue is comparison-based, the whole run is a comparison-based sorting algorithm for $V-1$ numbers, so by the decision-tree bound proved for merge sort it must perform \Omega(V \log V) comparisons in the worst case. Together with the $\Omega(E)$ needed to read the edges,

\begin{equation}T \;\in\; \Omega\big(E + V \log V\big)\end{equation}

for every implementation with a comparison-based priority queue, which is exactly the Fibonacci-heap upper bound. In that model Dijkstra with a Fibonacci heap is optimal, and the binary heap's extra \log V factor on the $E$ term is the price of its cheaper decrease-key.

Which variant to use. Comparing $V^2$ with (V+E)\log V, the array beats the binary heap exactly when E \in \omega(V^2/\log V), i.e. on dense graphs; on sparse graphs, where $E = O(V)$, the heap gives O(V \log V) against the array's \Theta(V^2).

Space. The arrays d, \mathit{parent}, \mathit{done} and the queue (with its index mapping vertices to heap positions, needed to locate a vertex for decrease-key) each occupy $\Theta(V)$ words, so the auxiliary space is $\Theta(V)$, on top of the $\Theta(V+E)$ input.

The Fundamental Functions of Algorithmic Analysis

Almost every running time met in practice is one of a dozen or so functions. The table below collects them in increasing order of growth, together with the structure that produces each one and the standard algorithms that realize it. Reading it downwards is a good way to calibrate intuition: each row is asymptotically dominated by every row below it, so a single step down the ladder costs more than any constant factor of tuning can ever recover.

Growth	Name	Where it comes from	Typical examples
$\Theta(1)$	Constant	A fixed number of primitive operations, independent of the input size	Array indexing; fixed-width arithmetic and bitwise operations; assigning a primitive; stack push/pop and queue enqueue/dequeue; linked-list insertion at a known node; hash-map insert and lookup on average (worst case $\Theta(n)$ when all keys collide)
\Theta(\alpha(n))	Inverse Ackermann	Amortized cost of near-flat tree structures; a constant for every $n$ that fits in the universe	Union-find with path compression and union by rank: \Theta(m\,\alpha(n)) for $m$ operations on $n$ elements
\Theta(\log^{*} n), $\Theta(\log\log n)$	Iterated / doubly logarithmic	Recursions that reduce the input to its logarithm at each step	Interpolation search on uniform data; van Emde Boas trees; some specialized parallel and geometric structures
$\Theta(\log n)$	Logarithmic	Each step discards a constant fraction of the remaining input	Binary search; search, insertion and deletion in a balanced BST (AVL, red-black, B-tree); binary-heap insert and extract-min; exponentiation by squaring; Euclid's GCD; fast-doubling Fibonacci
$\Theta(\log^k n)$	Polylogarithmic	A constant number of nested logarithmic searches	Multi-level indexing; range trees; many dynamic-connectivity structures
\Theta(\sqrt{n})	Square root	Block decompositions that balance \sqrt{n} blocks of \sqrt{n} elements	Trial-division primality testing; sqrt decomposition and Mo's algorithm; number-theoretic sieving steps
$\Theta(n)$	Linear	A constant amount of work for each element, once	Minimum/maximum of an array; linear search; traversing a linked list; insertion or deletion at an arbitrary position; comparing two arrays or strings; counting sort over a fixed alphabet
$\Theta(n\log n)$	Linearithmic	$\Theta(\log n)$ divide-and-conquer levels, each doing $\Theta(n)$ work, and the optimum for comparison sorting	Merge sort, heap sort, quicksort (average case); the Fast Fourier Transform; sorting-based sweeps and convex hulls
$\Theta(n^2)$	Quadratic	Two nested loops over the input: \sum_{i=1}^{n}\sum_{j=1}^{n} 1 = n^2	Selection and bubble sort; insertion sort in the worst case ($\Theta(n)$ when already sorted); naive substring search; all pairwise distances; Dijkstra with an array queue
$\Theta(n^3)$	Cubic	Three nested loops over the input	Naive matrix multiplication (Strassen's algorithm improves it to \Theta(n^{\log_2 7}) at the cost of a large constant); Floyd–Warshall all-pairs shortest paths
$\Theta(2^n)$	Exponential	One branch per binary choice: a set of $n$ elements has \sum_{k=0}^{n}\binom{n}{k} = 2^n subsets	Brute-force subset sum; naive recursive Fibonacci; enumerating all subarrays, which is \Theta(n\,2^n)
$\Theta(n!)$	Factorial	One branch per ordering of the input. By Stirling's approximation n! = 2^{\Theta(n\log n)}, so the factorial sits strictly between $\Theta(2^n)$ and $\Theta(n^n)$	Brute-force traveling salesman; generating all permutations of a set
$\Theta(n^n)$	Exponential with a growing base	Each of $n$ positions chooses independently among $n$ values, rather than consuming one of them as a permutation does, hence n^n/n! \approx e^n	Enumerating all functions from an $n$-element set to itself, or all $n$-colorings of $n$ items; brute force over all labelled trees, of which there are n^{n-2}
\Theta\!\left(2^{2^{n}}\right) and beyond	Doubly exponential, non-elementary, Ackermannian	Decision procedures whose search space is itself exponential in an exponential, or past that, bounded by no fixed tower of exponentials at all. These are the mirror image of the \alpha(n) row at the top of the table	Buchberger's algorithm for Gröbner bases and quantifier elimination over the reals (both doubly exponential); deciding Presburger arithmetic (triply exponential); deciding monadic second-order logic on strings (non-elementary); Petri-net reachability (Ackermann-complete)

References

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (CLRS).
Robert Sedgewick and Kevin Wayne. Algorithms, 4th edition.
Donald E. Knuth. The Art of Computer Programming.
Practical algorithm notes and proofs. https://cp-algorithms.com/.
Big-O notation. Reference for definitions and properties. https://en.wikipedia.org/wiki/Big_O_notation.