You are given a very long stream and you need to compute the running median for each group of 1k numbers. Same question for the running median. What is the complexity?
Suppose you know a priori the number of elements in the stream.
given a running average, you can update the group by adding a new element and removing the oldest one. This will give you a solution that is linear in the number of elements in the stream
Similar intuition is for the median, you can use a balanced BST where every node has the number of nodes contained in the subtree rooted at it.