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