Answer TRUE or FALSE.

The worst case lower bound for sorting an array is O(n \log n) since this is the cost of the best algorithm (in the worst case) that we know about.

False
  • True
  • False

Just because we don't know of a better algorithm does not mean that there is no better algorithm.

While it is true that the lower bound for sorting is O(n \log n), this is not the right reason.

The right reason is because we can prove that no algorithm can do better.