Typically ω-notation means an asymptotic lower bound on a problem. Generally these can be hard to find. f(n) is in ω(g(n)) if for all c > 0 there exists N > 0

Typically ω-notation means an asymptotic lower bound on a problem. Generally these can be hard to find. f(n) is in ω(g(n)) if for all c > 0 there exists N > 0 such that c|g(n)| <= |f(n)| for all n >= N