Time complexity for a sorted container

user_7932091 0
Viewed 708

I'm using Python's SortedDict container for a problem and was wondering what the time complexity of the getting the highest key would be:

from sortedcontainers import SortedDict
treeMap = SortedDict()
treeMap[1] = [4]
treeMap[1].append(6)
treeMap[3] = [9]
print(treeMap.keys()[-1]) # get the highest key in the sorted dictionary, should be 3

I know that most operations in SortedDict are O(log(n)) but I'm specifically confused about treeMap.keys()[-1]. For a normal dictionary, d.keys() is O(1) in python3..is d.keys()[-1] O(1) as well? Is it log(n) in case of sorteddict or O(n) as I need to access the last element?

complexity-theory time python
1 Answers

The sortedcontainers SortedDict maintains the key order, under the covers, in a sortedcontainers.SortedList. So the operation you're asking about is really SortedList.__getitem__(). From the docs:

__getitem__(index)[source] Lookup value at index in sorted list.

sl.__getitem__(index) <==> sl[index]

Supports slicing.

Runtime complexity: O(log(n)) – approximate.

So it's log time.

user_27055420
Related