Big Omega Notation

overview

Summary

big_omega_notation gives an asymptotic lower_bound. f(n) is in Ω(g(n)) if there exist constants c>0 and n0 with f(n) >= c*g(n) for all n >= n0. It captures a guaranteed_minimum growth_rate in asymptotic_analysis. Use it to state an algorithm cannot be faster than some function beyond a threshold. Contrast with big_o_notation (upper_bound) and big_theta_notation (tight_bound). Remember: lower bound, constants, threshold n0, and Ω means at least up to a constant_factor.