complexity theory - Upper bound vs lower bound for worst case running time of an algorithm

Question

I am learning about analysis of algorithms. I understand the concept of the worst case running time of an algorithm.

However, what are upper and lower bounds on the worst case running time of an algorithm?

What can be an example where an upper bound for the worst case running time of an algorithm is different from the lower bound for the worst case running time of the same algorithm?

Answer 1

For a function f(n), g(n) is an upper bound (big O) if for "big enough n", f(n)<=c*g(n), for a constant c. [g dominates f]
g(n) is lower bound (big Omega) if for "big enough n", f(n) >= c*g(n), for a constant c. [f dominates g]

If g(n) is both upper bound and lower bound of f(n) [with different c's], we say g(n) is a tight bound for f(n) [Big theta]

Use example for upper bound instead of tight one: Sometimes, it is hard to find tight bound, such as the fibonacci recursive algorithm. So we find an easy upper bound of O(2^n) easily. more info is found in answers in this post.

How does it related to worst/base/... cases? (as requested by comments):

Worst case/average case (or any other case) affects what the complexity function is, but big-O, big-Omega, and big-Theta can be applied to each of these cases.

For example, a HashTable insert is Θ(1) average case insertion, and Θ(n) worst case insertion. It is also O(n) average case insertion (bound is not tight), and Ω(1) worst case insertion.