Solution Set 2

Solution 1

Big O notation denotes an upper bound but is silent about the lower bound. Treat it like a cap on the worst that can happen. So when someone says that an algorithm has a lower bound of O(n²) that translates into saying the lower bound can at worst be quadratic in complexity. By definition, the lower bound is the best an algorithm can perform. Combine the two statements and your friend is saying the algorithm he found in the best case can perform in quadratic time or better. It can also perform in linear time or constant time, we just don't know. So your friend is effectively not telling you anything about the lower bound on the performance of his new found algorithm.

Solution 2

We can employ the Big O definition we learnt earlier to determine if O(2²ⁿ) and O(2ⁿ) are equivalent. Intuitively, it would feel 2²ⁿ will yield a greater number than 2ⁿ for values of n > 0. According to Big O definition:

$$0\leq f(n) \leq cg(n)$$ ...