Ryan and Brandon are arguing about the solution to your upco

Ryan and Brandon are arguing about the solution to your upcoming homework assignment on sorting algorithms. Ryan claims that his O(n log n)-time solution is always faster than Brandon\'s O(n^2) solution. However, Brandon claims that he ran several experiments on both algorithms on his laptop and sometimes his was faster. Explain what probably happened.

Solution

In respect of the given Big oh notation, the maximum time requirement of ryan\'s algorithm is less. But on practical execution of both the algorithms on differ data sets, it might happen that the datasets are such that Brandon\'s algorithm executes in best case or near best case scenario whereas ryan\'s algorithm exectes in worst case scenario, thereby taking more time than brandon\'s algorithm. Here, the main assumption made is that the best case of Brandon\'s algorithm is less than the worst case of Ryan\'s algorithm i.e. less than O(nlog n). Hence, there can be situation where brandon\'s algorithm takes less time than ryan\'s algorithm.