Course: Data Structures and Algorithms
What's the practical difference between saying an algorithm is O(n log n) and Theta(n log n)?
O(n log n) is an upper bound: the running time grows no faster than n log n, but it could grow more slowly. Theta(n log n) is a tight bound: the running time grows exactly at that rate, up to constant factors. In casual use people often say O when they mean Theta. When precision matters — for example comparing merge sort (Theta(n log n) always) with quicksort (O(n^2) worst case, Theta(n log n) average) — the distinction is important.