Search code examples
time-complexitycomplexity-theory

an algorithm that is Theta(n) is also O(n^2), is this correct?


As Theta(n) is about the upper and lower bound, this question confused me. I am sure O(n) can be O(n^2), but Omega(n) is also O(n^2)?


Solution

  • Bear in mind that O(f),Theta(f), Omega(f) are sets of functions.

    O(n) is the set of functions that asymptotically grow at most as fast as n (modulo a constant factor), so O(n) is a proper subset of O(n^2).

    Omega(n) is the set of functions that asymptotically grow at least as fast as n, so it is definitely not a subset of O(n^2). But it has a non-empty intersection with it, for example 0.5n and 7n^2 are in both sets.