The best case, worst case, and expected case

If we simplify things, then we can think of the efficiency of our algorithms in terms of best case, worst case, and expected case. The best case is when the input of our algorithms meets some extraordinary conditions that allow it to perform the best. The worst case is at the other extreme, where the input is in an unfavorable shape that makes our algorithm reveal its worst performances. Commonly, however, these amazing or terrible situations won't happen. So, we introduce the expected performance.

Most of the time, we care about the worst and expected cases, which, in the case of most algorithms, are usually the same. The best case is an idealistic performance, and so it remains idealistic. Mainly, for almost any algorithm, we can find a special input that will lead to the O(1) best-case performance.

For more details about Big O, I strongly recommended you read the Big O cheat sheet (https://www.bigocheatsheet.com/).

Now,...