educative.io

Educative

Brute force approach :Median of stream of numbers

Hi,
Could someone the following statement in the solution explanation for the brute force approach.
Inserting a number in a sorted list will take O(N), time if there are ‘N’ numbers in the list. This insertion will be similar to the Insertion sort
The worst and average case Time complexity for insertion sort = O(n^2)
Only in the best case is it O(n)
Not sure in what scenario will it be O(n)

You are getting it wrong. This insertion will be similar to the Insertion sort in that sense if we use the approach to sort the elements first and then find median of stream of numbers. Likewise approach is used in insertion sort too.