CODEWITHSUNDEEP
time-complexitycomplexity-theory
Fred
Fred

Reputation: 344

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)?

Upvotes: 0

Views: 214

Answers (1)

Mo B.
Mo B.

Reputation: 5805

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.

Upvotes: 1

Related Questions