Big-Theta Notation

Math for CS · Axiom Academy

Tight asymptotic bounds: pinning down exact growth rates Big-Theta combines Big-O and Big-Omega into a single, tight bound. It says a function grows at exactly the rate of another, up to constant factors. Definition: We say if there exist positive constants , , and such that: This means is "sandwiched" between two constant multiples of . The function grows at the same rate as . Equivalent formulation: if and only if and . Upper bound (Big-O): For : . So . Lower bound (Big-Omega): For : . So . The pattern: For any polynomial with 0"> , the polynomial is . The leading term determines the growth rate. Not every pair of functions has a Big-Theta relationship. only works when the upper and lower bounds match. Example where Big-Theta fails: because but . The growth rates differ. Also, Big-Theta does not apply well to algorithms whose best and worst cases have different growth rates: Insertion sort: Best case (already sorted), worst case (reverse sorted). We cannot say the running time is or in general — it depends on the input. However, the worst-case running time of insertion sort is , and the best-case running time is . Precision matters: Be specific about what you are bounding. "The worst-case time is " is precise. "The running time is " is ambiguous if best and worst cases differ. The Complete Picture: O, Omega, Theta Limit test (useful shortcut): If where , then . If , then but not (f grows strictly slower). If , then but not (f grows strictly faster).

This is the written version of the interactive lesson above. See the full Math for CS course.