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