Introduction

The mean and median behave very differently from an algorithmic point of view. The mean can be returned in constant time if you maintain enough summary information as data changes. The median is harder: for arbitrary dynamic data, you cannot generally support both unrestricted updates and exact constant-time recomputation without stronger assumptions about the input domain or preprocessing model.

The Mean Really Can Be Constant Time

If you store the running sum and the number of elements, the mean is just sum / count.

1class RunningMean:
2    def __init__(self):
3        self.total = 0.0
4        self.count = 0
5
6    def add(self, value):
7        self.total += value
8        self.count += 1
9
10    def mean(self):
11        if self.count == 0:
12            raise ValueError("no values")
13        return self.total / self.count
14
15m = RunningMean()
16for x in [10, 20, 30]:
17    m.add(x)
18
19print(m.mean())

The query is constant time because the work was pushed into updates. If you also support deletion, maintain the same fields in reverse.

Why Median Is Different

The median depends on relative ordering, not just on a small summary such as a sum. A single new value can change which element is in the middle, so exact median maintenance usually needs an ordered view of the data.

For an unsorted collection with arbitrary inserts, exact median lookup is not something you can recompute from a tiny fixed-size summary. That is why there is no general-purpose equivalent of “keep a sum and divide.”

The Practical Dynamic Solution: Two Heaps

For streaming data, the standard exact solution is two heaps:

• a max-heap for the lower half,
• a min-heap for the upper half.

This gives:

• 'O(log n) insertion,'
• 'O(1) median query.'

1import heapq
2
3class RunningMedian:
4    def __init__(self):
5        self.low = []
6        self.high = []
7
8    def add(self, value):
9        heapq.heappush(self.low, -value)
10
11        if self.high and -self.low[0] > self.high[0]:
12            heapq.heappush(self.high, -heapq.heappop(self.low))
13
14        if len(self.low) > len(self.high) + 1:
15            heapq.heappush(self.high, -heapq.heappop(self.low))
16        elif len(self.high) > len(self.low):
17            heapq.heappush(self.low, -heapq.heappop(self.high))
18
19    def median(self):
20        if not self.low and not self.high:
21            raise ValueError("no values")
22        if len(self.low) == len(self.high):
23            return (-self.low[0] + self.high[0]) / 2
24        return -self.low[0]
25
26rm = RunningMedian()
27for x in [10, 20, 30, 40]:
28    rm.add(x)
29    print(rm.median())

This is usually what people really want when they ask for “constant time median” in an online setting.

When Median Can Be Constant Time

There are special cases where exact constant-time lookup is realistic.

One example is a bounded value domain. If values are known to be integers in a small fixed range, you can maintain a frequency table. In that case, lookup may be treated as constant time relative to input size because the domain size is fixed.

1class SmallDomainMedian:
2    def __init__(self, max_value):
3        self.freq = [0] * (max_value + 1)
4        self.count = 0
5
6    def add(self, value):
7        self.freq[value] += 1
8        self.count += 1
9
10    def median(self):
11        target = (self.count - 1) // 2
12        seen = 0
13        for value, f in enumerate(self.freq):
14            seen += f
15            if seen > target:
16                return value

This is only “constant” if the domain bound is treated as a fixed constant, not as part of the problem size.

Query Time Versus Update Time

A lot of confusion comes from mixing these two questions:

• Can I answer the query in O(1)?
• Can I maintain the data structure with O(1) updates too?

For the mean, both can be close to constant-time under simple insert and delete rules. For the exact median on arbitrary values, constant-time query is possible with maintained structure, but not constant-time update in the general comparison-based case.

So the honest answer is usually:

• mean: yes,
• median: not in the fully general dynamic case, but O(1) query with O(log n) update is standard.

Common Pitfalls

• Claiming the median can be maintained like the mean with only a running total and count.
• Forgetting to distinguish query complexity from update complexity.
• Calling something constant time when it depends on scanning a non-constant value domain.
• Using full sorting after every insertion when online median structures exist.
• Ignoring whether the data is static, streaming, or deletion-heavy.

Summary

• The mean can be returned in constant time if you maintain a running sum and count.
• The exact median is harder because it depends on ordering, not just a simple summary.
• Two heaps give a practical exact solution with O(log n) update and O(1) query.
• Special bounded-domain cases can make median lookup effectively constant relative to data size.
• Always separate the cost of answering the query from the cost of maintaining the data structure.