CPP CPP Algorithms & Complexity Analysis 1 — Questions and Answers
Question 1: What is the time complexity of std::sort in C++?
- O(n)
- O(n log n) (Correct answer)
- O(n²)
- O(log n)
Correct answer: O(n log n)
std::sort uses introsort, a hybrid algorithm that guarantees O(n log n) average and worst-case time complexity.
Question 2: Which STL container provides O(1) average time for insertion and lookup?
- std::vector
- std::list
- std::unordered_map (Correct answer)
- std::map
Correct answer: std::unordered_map
std::unordered_map uses a hash table internally, giving O(1) average time for insertions and lookups.
Question 3: What is the call-stack space complexity of a naive recursive Fibonacci implementation?
- O(1)
- O(n) (Correct answer)
- O(n²)
- O(2^n)
Correct answer: O(n)
The call stack depth reaches at most O(n) for recursive Fibonacci, even though the number of calls is exponential.
Question 4: Which algorithm is best suited for finding the shortest path in an unweighted graph?
- Depth-first search
- Dijkstra's algorithm
- Breadth-first search (Correct answer)
- A* search
Correct answer: Breadth-first search
Breadth-first search guarantees the shortest path in an unweighted graph by exploring nodes level by level.
Question 5: What does std::lower_bound return on a sorted range?
- The minimum element
- An iterator to the first element not less than the given value (Correct answer)
- The maximum element
- An iterator to the last element less than the given value
Correct answer: An iterator to the first element not less than the given value
std::lower_bound returns an iterator to the first element in a sorted range that is not less than (>= ) the given value.
Question 6: What is the time complexity of inserting an element at the beginning of a std::vector?
- O(1)
- O(log n)
- O(n) (Correct answer)
- O(n log n)
Correct answer: O(n)
Inserting at the beginning of std::vector requires shifting all existing elements, resulting in O(n) time complexity.
CPP CPP Algorithms & Complexity Analysis 1
What is the time complexity of std::sort in C++?