CPP CPP Algorithms & Complexity Analysis 1

Question 1

What is the time complexity of std::sort in C++?

Accepted Answer

O(n log n)

Answer

O(n)

Answer

O(n²)

Answer

O(log n)

Question 2

Which STL container provides O(1) average time for insertion and lookup?

Accepted Answer

std::unordered_map

Answer

std::vector

Answer

std::list

Answer

std::map

Question 3

What is the call-stack space complexity of a naive recursive Fibonacci implementation?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(n²)

Answer

O(2^n)

Question 4

Which algorithm is best suited for finding the shortest path in an unweighted graph?

Accepted Answer

Breadth-first search

Answer

Depth-first search

Answer

Dijkstra's algorithm

Answer

A* search

Question 5

What does std::lower_bound return on a sorted range?

Accepted Answer

An iterator to the first element not less than the given value

Answer

The minimum element

Answer

The maximum element

Answer

An iterator to the last element less than the given value

Question 6

What is the time complexity of inserting an element at the beginning of a std::vector?

Accepted Answer

O(n)

Answer

O(1)

Answer

O(log n)

Answer

O(n log n)