Difficulty: Intermediate | Prerequisites: Undergraduate algorithms (sorting, Big-O notation), basic set theory
This material sits at the start of a graduate-level algorithms course and revisits two foundational questions: how do we formally characterise the time complexity of well-known sorting algorithms, and what are the fundamental limits of comparison-based computation? If you are coming in cold, the key thing to know is that Big-O notation describes an upper bound on running time (for all inputs), while Big-Omega describes a lower bound (there exists some input that forces at least this much work). Confusing the two is one of the most common early mistakes in this course.
These topics connect to everything that follows in CSCE 629. Decision-tree arguments reappear in lower bounds for sorting and selection, and the precise handling of O-notation is expected throughout.
Quicksort runs in O(n²) but not O(n log n), because its worst case is quadratic. Mergesort runs in O(n log n) and therefore also O(n²), since n log n is bounded above by n². Any comparison-based search on n elements requires at least Omega(log n) comparisons in the worst case, proved via a decision-tree argument that counts the minimum number of distinguishable leaves.
Big-O notation, O(f(n))
An algorithm runs in time O(f(n)) if there exists a constant c such that for all n, its running time is at most c · f(n). It is an upper bound that must hold for every input of size n.
In simple terms, this means the algorithm never does worse than roughly f(n) steps, no matter what input you give it.
Big-Omega notation, Ω(f(n))
An algorithm (or problem) has a lower bound of Ω(f(n)) if there exists a constant c such that for infinitely many n, some input forces at least c · f(n) steps.
Think of it as: no matter how clever you are, some input will force you to do at least this much work.
Decision tree
A binary tree that models a comparison-based algorithm. Each internal node is a comparison, each branch is an outcome, and each leaf is a final answer. The height of the tree equals the worst-case number of comparisons.
In simple terms, it is a map of every possible path an algorithm could take, drawn out as a tree.
Worst-case running time
The maximum number of steps an algorithm takes over all possible inputs of size n. When we say an algorithm "takes time O(f(n))," we mean the worst-case time is bounded by c · f(n).
Quicksort is NOT O(n log n).
The worst case for Quicksort is Ω(n²). That is, there exist inputs (for every n) where Quicksort performs at least c · n² comparisons.
Because O-notation requires the bound to hold for all inputs, you cannot claim O(n log n) when some inputs take quadratic time.
Students sometimes confuse average-case O(n log n) with worst-case. The O-notation claim here is about worst-case behaviour.
Quicksort IS O(n²).
On every input of size n, Quicksort makes at most c · n² comparisons for some constant c.
This is the tightest worst-case upper bound for standard Quicksort.
Mergesort IS O(n log n).
Mergesort always divides the input evenly and merges in linear time, giving a worst-case bound of c · n log n.
Mergesort IS also O(n²).
Since n log n ≤ n² for all n ≥ 1, any function bounded by c · n log n is automatically bounded by c · n².
By the definition of O-notation, Mergesort therefore also runs in O(n²). This is a weaker (less informative) but still correct statement.
This illustrates a key principle: O-notation gives an upper bound, not a tight bound. Saying Mergesort is O(n²) is true but not useful.
The question "Is Quicksort O(n log n)?" tests whether you understand that O-notation is a claim about all inputs. The average-case behaviour is irrelevant. If even one family of inputs forces quadratic time, the O(n log n) claim is false.
Problem: Given a set S of n elements and a query x, determine whether x ∈ S using only element comparisons.
The decision-tree model:
Any comparison-based search algorithm can be represented as a decision tree T.
Internal nodes are comparisons; leaves are conclusions ("Yes, x ∈ S" or "No, x ∉ S").
For a given input (S, x), the algorithm follows exactly one root-to-leaf path.
Counting distinct Yes-leaves:
Fix S = {1, 2, ..., n}. For each integer i in S, the input (S, i) must reach a Yes-leaf.
Two distinct elements i and j (with i < j) must reach different leaves. The proof uses the intermediate value i + 0.5:
If inputs (S, i) and (S, j) followed the same path, then (S, i + 0.5) would follow that same path too (every comparison outcome is identical for i + 0.5 as for both i and j, since i < i + 0.5 < j means i + 0.5 has the same ordering relationship to every element of S along that path).
But i + 0.5 ∉ S, so the algorithm should return No, not Yes. Contradiction.
Therefore there are at least n distinct Yes-leaves, plus at least one No-leaf, giving at least n + 1 leaves total.
From leaf count to height:
A binary tree with at least n leaves has height h ≥ ⌊log n⌋.
Some input must follow a path of length h, making at least h − 1 comparisons.
Therefore the worst-case number of comparisons is Ω(log n).
O-notation definition: T(n) = O(f(n)) iff ∃c > 0, ∃n₀ such that T(n) ≤ c · f(n) for all n ≥ n₀
Ω-notation definition: T(n) = Ω(f(n)) iff ∃c > 0 such that T(n) ≥ c · f(n) for infinitely many n
Binary tree leaf-height relationship: A binary tree with L leaves has height h ≥ ⌊log₂ L⌋
Key inequality used: n log n ≤ n² for all n ≥ 1
Binary search is the classic example of an O(log n) comparison-based search, and this lower bound tells you it is essentially optimal: no comparison-based method can do fundamentally better in the worst case. This is why databases, search engines, and operating systems all rely on sorted structures and binary search as a bedrock operation.
"Quicksort is O(n log n)." It is not, in the worst-case sense. Students conflate average-case performance with worst-case O-notation. The O-notation claim requires the bound to hold for all inputs.
"O(n²) means the algorithm is slow." Not necessarily. O-notation gives an upper bound. Saying Mergesort is O(n²) is technically correct, just not the tightest bound available. The statement tells you less than O(n log n) does, but it is not wrong.
"The lower bound proof means every search takes log n steps." The lower bound is a worst-case statement. Some inputs may be found faster. The point is that some input will require at least Ω(log n) comparisons for any algorithm.
"The intermediate-value trick (i + 0.5) is a special case." It is actually a general technique. The argument works for any value strictly between two elements that is not in S, and it generalises to other lower bound proofs.
⚠️ The Quicksort O(n log n) question is a classic exam trap. Know that O-notation is about all inputs, not average or best case.
⚠️ The decision-tree lower bound technique for searching is a warm-up for the Ω(n log n) sorting lower bound, which uses the same framework. Expect to see it again.
⚠️ Be able to reproduce the counting argument: n distinct inputs require n distinct leaves, a binary tree with n leaves has height at least log n.
⚠️ Understand why i + 0.5 works in the proof. The examiner may change the problem (e.g., finding the rank of an element) and expect you to adapt the same argument.
True or false: An algorithm with average-case O(n log n) and worst-case O(n²) can be described as O(n log n).
A: False. O-notation (without further qualification) refers to worst-case, and the worst case is O(n²), not O(n log n).
Fill in the blank: A binary tree with at least L leaves has height at least ___.
A: ⌊log₂ L⌋
True or false: Mergesort is O(n³).
A: True. It is a valid but unhelpfully loose upper bound, since Mergesort is also O(n log n).
True or false: The comparison-based search lower bound of Ω(log n) applies to hash-table lookups.
A: False. Hash tables are not comparison-based; they use hashing, not element comparisons.
Q: Explain why Quicksort cannot be O(n log n) using the formal definition of O-notation.
A: For Quicksort to be O(n log n), there must exist a constant c' such that its running time is at most c' · n log n for all n and all inputs of size n. But Quicksort's worst case is Ω(n²), meaning there exist inputs where it takes at least c · n² time. Since n² grows faster than n log n, no constant c' can make c' · n log n ≥ c · n² for all n. Therefore the O(n log n) claim fails.
Q: In the search lower bound proof, why must inputs (S, i) and (S, j) with i ≠ j reach different leaves in the decision tree?
A: If they reached the same leaf via the same path, then the fictitious input (S, i + 0.5) with i < i + 0.5 < j would follow that same path (all comparisons yield the same outcomes). But i + 0.5 ∉ S, so it should reach a No-leaf, not the Yes-leaf that i and j reach. This contradiction proves the paths must differ.
Q: Why does Mergesort being O(n log n) automatically make it O(n²)?
A: Because n log n ≤ n² for all n ≥ 1. If the running time T(n) ≤ c · n log n, then T(n) ≤ c · n², satisfying the O(n²) definition.
Q: Could a comparison-based search algorithm beat O(log n) on average, even though the worst case is Ω(log n)?
A: Yes. The lower bound is worst-case only. If the input distribution is known (e.g., uniform), an algorithm could achieve fewer comparisons on average. But some input will always require Ω(log n) comparisons.
This connects to the sorting lower bound (Ω(n log n) for comparison-based sorting), which uses an almost identical decision-tree argument but counts n! permutations instead of n search outcomes. It also connects to the study of 2-3 trees and balanced search structures later in the course, where O(log n) search time is achieved by maintaining tree balance.
Big-O notation, Big-Omega notation, asymptotic analysis, worst-case complexity, Quicksort, Mergesort, comparison-based algorithms, decision tree model, search lower bound, binary tree height, leaf counting argument, CSCE 629, analysis of algorithms, Texas A&M, sorting complexity, upper bound vs lower bound, average case vs worst case