big-ocomplexity-theory

Does the value of n matter when comparing asymptotic complexities?


Is the complexity defined by the big-O notation e.g., n! is always more complex than n^3, regardless of the value of n?

What if I know n = 3? Would I be able to say that in this case O(n!) is less complex than O(n^3)?


Solution

  • In any sort of expression like this, you have to know what the independent variable is.

    For example, the expression ab is polynomial in a (holding b constant) but exponential in b (holding a constant).

    When we write O(n!) or O(n3), usually the situation is that n is the independent variable, and we're interested in how n! and n3 grow as n grows; but if n is actually constant, then n! and n3 are both constant, and O(n!) = O(n3) = O(1): these expressions don't grow as m grows, or p grows, or whatever our independent variable is grows.