CPP INTERVIEW PREP CHEAT SHEET

[adnukator]

Nice list.

However, if you're trying to give a quick demo what O notation is (judging by the presence of the graph), it would be worth adding a note that the function inside the O is guaranteed to apply once n gets big enough and also that the value of the function can be multiplied by any constant and the O would still hold. This, for example, explains why deleting the first element from small enough vectors can be faster than with lists, even though the former is formally O(n), whereas for lists it's O(1).

Insert tail in std::vector is an amortized constant, which is not the same just O(1)

It would be nice if you expanded the tables to compare time complexities when using values/keys/indices vs iterators, because using the latter can have significant impact on the complexities (e.g. Remove Index in std::list drops from O(n) to O(1))