Describes a lower bound for a given function as its input size increases to infinity.
Definition
Let define to be the set of functions s.t
Equivalently,
Describes a lower bound for a given function as its input size increases to infinity.
Let g∈F define Ω(g) to be the set of functions f∈F s.t ∃b∈R+,∃n0∈N,∀n∈N,n>n0⟹f(n)≥b⋅g(n)≥0
Equivalently, f∈Ω(g)⟺g∈O(f)