CODEWITHSUNDEEP
asymptotic-complexity
MNRC
MNRC

Reputation: 175

Theta vs. Omega

I'm trying to understand time complexity.

If you have an algorithm with a running time of θ(n^2), is it possible to have a best case running time of Ω(n)? Or is the fastest running time only some constant factor c * n^2?

Upvotes: 1

Views: 58

Answers (1)

PhilHQ
PhilHQ

Reputation: 58

Theta is a tight bound, meaning that it represents the worst case and the best case. So in your case, the fastest running time will be a constant of the tight bound.

Upvotes: 1

Related Questions