waww waww - 4 days ago 5
Python Question

What is Big-O of this setitem method?

What is time complexity of this

__setitem__
method for empty dictionary? I think that, .key and .value python methods for dictionary are O(n) ( I read it somewhere) and for loop is also O(n). My guess is O(n)*O(n)*O(n)+O(1) = for loop + if + if body + append. But Im not sure with that "if in for loop body" situation and the .item and .value being O(n).

Please help. It was on my school test. Code is in python.

def __setitem__(self,k,v):
for item in self._table:
if k == item._key:
item._value = v
return
self._table.append(self._Item(k,v))

Answer

It is O(len(self._table)) (assuming constructing self._Item is O(1)) because in the worst case you need to check every element in the self._table object.

Both the if statement and its body will be O(1) in terms of the input because they're atomic operations. Thus, the for-loop's complexity is O(n) * O(1) * O(1) == O(n) where n is the size of self._table.

append is an atomic operation for lists, so it's amortized O(1), but if you reach this operation, you've already done O(n) work, so it makes the method O(n).

Comments