Delete all keys in Python dictionary greater than x in constant time-CodePudding

If you have a dictionary:

d = {1: True, 2: False, 3: False, 4: True, 5: False, 6: True, 7: False, 8: False}

and you want all keys greater than 3 to be deleted so the dictionary becomes:

{1: True, 2: False, 3: False}

can you do this in constant time if the keys are sorted?

CodePudding user response：

No, we cannot do it in constant time.

To remove all the keys greater than 3 we can simply do:

{k:v for k,v in d.items() if k<=3} 
#{1: True, 2: False, 3: False}

We have a for-loop in above dictionary comprehension. Its time complexity is O(n).

However, you can access individual elements in constant time, like:

d[3]
#False   constant Time complexity O(1)

CodePudding user response：

if you always want to go upto a fixed number, say k; doing this might be a good solution:

new_dict = {}
for i in range(1,k 1):
    new_dict[i] = old_dict[i]

Since the k is fixed, its constant time complexity

According to this answer, accessing a dictionary is practically just constant time.