I was reading a solution to the problem in the title on leetcode and the article says that the time complexity of the following solution is O(n)
- setup a data structure to hold stream value and insert new element in the right place using linear search or binary search
- return median
my solution is as follows:
class MedianFinder: def __init__(self): """ initialize your data structure here. """ self.arr = () def addNum(self, num: int) -> None: idx = bisect.bisect_left(self.arr, num) self.arr.insert(idx, num) def findMedian(self) -> float: # self.arr.sort() if len(self.arr) % 2 != 0: return self.arr(len(self.arr)//2) else: return (self.arr(len(self.arr)//2 -1) + self.arr(len(self.arr)//2 ))/2
My question is about the time complexity of the push method. the binary search will take O(log n) to find the index. the insert will take O(n). but since the method will be called on the stream, will the complexity be O(n^2) or O(n) ?