Tight Bound
← Back to Big-Theta Notation
A function f(n) is Theta(g(n)) when it is both O(g(n)) and Omega(g(n)). A tight bound precisely characterizes the growth rate, meaning the algorithm always grows at exactly this rate asymptotically. For example, merge sort is Theta(n log n) since both its best and worst cases are n log n.