Answer the following statements true (T) or false (F)

1. Insertion into a vector runtime is O(1) at any position in the vector. Explain what ‘runtime is O(1)’ means.
2. Insertion into an STL list takes O(1) time at any position in the list. What does ‘ takes O(1) time’ mean?
3. STL ranges [first, last) are always ‘half-open’ – from the first element to a designation for one past the last element.
4. Given a map m, the expression m["value"] will return NULL if there is no string named "value" stored in the map.
5. Elements of a set and map are stored in sorted order.

1. False
Runtime is O(1) means there is an upper bound for the runtime that is independent of the size of the problem, which is the size of the vector in this case. Vector insertion is O(n) at any position in the vector except the back. Insertion is O(1) only for insertion at the back of the vector. For example, use of the push_back() member is O(1). There are other ways to insert most of which we do have not treated in the text, all of which are O(1) at the back.
2. True
An STL list is a linked structure. Insertion at any position involves only a half-dozen or so assignments and a free store allocation. This is O(1), which means there is a fixed upper bound for the insertion time that is independent of the size of the list.
3. True.
Note the begin() and end(),and the rbegin()and rend() member functions that all the sequence containers have. They provide a ‘half open’ range from the first element in the container to one past the last. The rbegin() and rend() members provide a range from the last to past the front, as a reverse_iterator would traverse.
4. False.
This will actually add a new entry to the map associated with the key "value" that has the default entry for the map container type.
5. True