In sortedContainers it is specified that SortedList.add
has approximately O(log(n)) time complexity, but we can see that it uses insort()
in the source code, which is O(n):
def add(self, value):
"""Add `value` to sorted list.
Runtime complexity: `O(log(n))` -- approximate.
>>> sl = SortedList()
>>> sl.add(3)
>>> sl.add(1)
>>> sl.add(2)
>>> sl
SortedList([1, 2, 3])
:param value: value to add to sorted list
"""
_lists = self._lists
_maxes = self._maxes
if _maxes:
pos = bisect_right(_maxes, value)
if pos == len(_maxes):
pos -= 1
_lists[pos].append(value)
_maxes[pos] = value
else:
insort(_lists[pos], value)
self._expand(pos)
else:
_lists.append([value])
_maxes.append(value)
self._len += 1
Can someone explain why the method still approximates to O(log(n)) despite the use of insort
?
Ok, from what I see in the code, SortedList uses set of lists to store the sorted list. The add
first finds the relevant sublist and then inserts into it with insort
, so it's linear on the length of the sublist, not the whole list. I suspect SortedList tries to keep length of each of the sublists bounded by log(whole list)
.