Big-Omega Notation

Math for CS · Axiom Academy

Asymptotic lower bounds: how slow must an algorithm be? While Big-O gives an upper bound ("at most this fast"), Big-Omega gives a lower bound ("at least this slow"). Definition: We say if there exist positive constants and such that: In plain English: past some threshold , the function is always at least . The growth of is bounded below by the growth of . Relationship to Big-O: if and only if . They are mirror images of each other. Proof: We need 0"> and such that for all . If for all large , then , which fails as . Big-Omega for Best Case and Lower Bounds Big-Omega has two important uses in algorithm analysis: Use 1: Best-case running time. An algorithm's best case is if even on the easiest inputs, it still takes at least steps. Example: Any comparison-based sorting algorithm has a best case of because it must at least examine each element once. Use 2: Lower bounds on problems. A problem has a lower bound of if every possible algorithm for that problem requires at least time. Example: Comparison-based sorting has a lower bound of . No comparison sort can beat this in the worst case. This is proven by a decision tree argument: there are possible orderings, and a binary tree with leaves has height at least . Big-O vs Big-Omega: Side by Side Symmetry: . Every Big-O statement has a mirror Big-Omega statement. When we can prove both and , we get the tightest possible characterization: , which is the subject of the next lesson. Determine whether each statement is true or false:

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