Simple but worth mentioning reason of why the best we can do in worst case is O(n)

  • 2

    For the worst case, i.e., all items are the same, the best we could possibly do is O(n). That is, we need to scan every item.

    The reason is actually quite straightforward and can be shown by contradictory: Suppose we skip some item with index i (if we don't skip any item, time complexity would be of O(n) as a minimum). We can end up with a wrong min value in the case when item at i is the minimum. Therefore, we cannot skip any index.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.