Alex Rivera | Logout

What is the difference between lower bound and tight bound?

Asked 2009-01-21T04:21:40.993
120

With the reference of this answer, what is Theta (tight bound)?

Omega is lower bound, quite understood, the minimum time an algorithm may take. And we know Big-O is for upper bound, means the maximum time an algorithm may take. But I have no idea regarding the Theta.

big-o
Edit
Report

1 Answer

188

Big O is the upper bound, while Omega is the lower bound. Theta requires both Big O and Omega, so that's why it's referred to as a tight bound (it must be both the upper and lower bound).

For example, an algorithm taking Omega(n log n) takes at least n log n time, but has no upper limit. An algorithm taking Theta(n log n) is far preferential since it takes at least n log n (Omega n log n) and no more than n log n (Big O n log n).

answered 2009-01-21T04:26:22.670

Your Answer