What is the difference between lower bound and tight bound?

Solution 1:

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

Solution 2:

Θ-notation (theta notation) is called tight-bound because it's more precise than O-notation and Ω-notation (omega notation).

If I were lazy, I could say that binary search on a sorted array is O(n²), O(n³), and O(2ⁿ), and I would be technically correct in every case. That's because O-notation only specifies an upper bound, and binary search is bounded on the high side by all of those functions, just not very closely. These lazy estimates would be useless.

Θ-notation solves this problem by combining O-notation and Ω-notation. If I say that binary search is Θ(log n), that gives you more precise information. It tells you that the algorithm is bounded on both sides by the given function, so it will never be significantly faster or slower than stated.