Complexity analysis interview questions

Quick facts

Recall the answer first, then tap Show to check.

• x in list costShowHide

  Membership in a list scans items one by one: O(n). In a set or dict it is O(1) on average.

• list.insert(0, x) costShowHide

  Inserting or deleting at the front of a list shifts every other item: O(n). deque.appendleft is O(1).

• str is immutableShowHide

  Python strings cannot change, so s += t in a loop may copy the growing string each time; ''.join(parts) builds it once in O(total length).

• sorted() costShowHide

  Python's sort is O(n log n) comparisons in the worst case and close to O(n) on input that is already mostly in order.

• pow(b, e, m)ShowHide

  The built-in three-argument pow computes modular powers by repeated squaring in O(log e) multiplications.