What is the time complexity of looking up a value by its key in a Python dictionary under average operational conditions?
Answer and explanation
Correct answer: A. O(1)
- Step 1: Recall that Python dictionaries are implemented using dynamic hash tables.
- Step 2: With an effective hash function and sparse hash collisions, computing the hash and accessing the bucket index executes in constant average time.
Answer
O(1).
Why not the others: is worst-case when all keys collide into the same bucket; is tree-based map lookup; is polynomial.
Practise more Algorithms and Python Programming.
Free questions with an explanation for every one, and full timed EmSAT Achieve (UAE) mock tests.
More Algorithms and Python Programming questions
- What is the output of the following Python expression: [x**2 for x in range(6) if x % 2 != 0]?
- What is the worst-case time complexity of searching for an element in a balanced binary search tree (AVL tree) containing n nodes?
- What will be printed by the following Python code snippet?
def func(val, lst=[]):
lst.append(val)
return lst
print(func(1))
print(… - Which abstract data structure operates on a First-In, First-Out (FIFO) ordering principle?
- What is the return value of executing the recursive Python function `mystery(4)`?
def mystery(n):
if n <= 1:
return 1
retur… - What is the worst-case time complexity of the standard QuickSort algorithm when the chosen pivot is consistently the smallest or largest ele…