How can SortedList.add have o(log(n)) time complexity when it uses insort internally?

Question

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 ?

Answer 1

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).