waww - 1 year ago 75

Python Question

What is time complexity of this

`__setitem__`

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 Source

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)`

.