# Time complexity of finding median in data stream

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)

1. setup a data structure to hold stream value and insert new element in the right place using linear search or binary search
2. return median

my solution is as follows:

class MedianFinder:

def __init__(self):
"""
"""
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) ?

From a brief look at Leetcode streaming problem solutions, the complexity solutions provided for streaming problems refer to the time complexity of a single iteration for the stream i.e. after $$n$$ elements in the stream, what is the complexity of updating the data structure and answering a query with a new element?