Search code examples
algorithmcomplexity-theory

In asymptotic notation why we not use all possible function to describe growth rate of our function?

if f(n) = 3n + 8,
for this we say or prove that f(n) = Ω(n)
Why we not use Ω(1) or Ω(logn) or .... for describing growth rate of our function?

Solution

  • In the context of studying the complexity of algorithms, the Ω asymptotic bound can serve at least two purposes:

    • check if there is any chance of finding an algorithm with an acceptable complexity;

    • check if we have found an optimal algorithm, i.e. such that its O bound matches the known Ω bound.

    For theses purposes, a tight bound is preferable (mandatory).

    Also note that f(n)=Ω(n) implies f(n)=Ω(log(n)), f(n)=Ω(1) and all lower growth rates, and we needn't repeat that.