CPP Algorithms & Complexity Analysis Flashcards
6 cards from real CPP practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 6 CPP Algorithms & Complexity Analysis flashcards as text
What is the time complexity of std::sort in C++?
Answer: O(n log n)
std::sort uses introsort, a hybrid algorithm that guarantees O(n log n) average and worst-case time complexity.
Which STL container provides O(1) average time for insertion and lookup?
Answer: std::unordered_map
std::unordered_map uses a hash table internally, giving O(1) average time for insertions and lookups.
What is the call-stack space complexity of a naive recursive Fibonacci implementation?
Answer: O(n)
The call stack depth reaches at most O(n) for recursive Fibonacci, even though the number of calls is exponential.
Which algorithm is best suited for finding the shortest path in an unweighted graph?
Answer: Breadth-first search
Breadth-first search guarantees the shortest path in an unweighted graph by exploring nodes level by level.
What does std::lower_bound return on a sorted range?
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.
What is the time complexity of inserting an element at the beginning of a std::vector?
Answer: O(n)
Inserting at the beginning of std::vector requires shifting all existing elements, resulting in O(n) time complexity.