Search code examples
algorithmcomplexity-theory

Arrange asymptotic functions according to growth rate

Arrange the following growth rates in the increasing order

O(n3),O(1),O(n2),O(nlogn),O(n2logn),Ω(n0.5),Ω(nlogn),Θ(n3),Θ(n0.5)

Solution

  • The Big Omega notation provides a lower bound to a function.

    So Ω(n^0.5) < Ω(n log n)

    The Big O notation provides an upper bound to a function.

    So O(n^3) > O(n^2 log n) > O(n^2) > O(n log n) > O(1)

    The Big Theta notation bounds a functions from above and below.

    So Θ(n^3) > Θ(n^0.5)