Free AMCAT Algorithm Complexity Questions and Answers

Question 1

What does Big O notation represent?

Accepted Answer

The worst-case time complexity or upper bound of an algorithm's growth rate.

Answer

The exact execution time of an algorithm.

Answer

The best-case time complexity of an algorithm.

Answer

The amount of memory an algorithm uses.

Question 2

What is the time complexity of a binary search algorithm on a sorted array of size 'n'?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(1)

Question 3

A nested loop where the outer loop runs 'n' times and the inner loop also runs 'n' times for each outer iteration will typically have a time complexity of:

Accepted Answer

O(n^2)

Answer

O(n)

Answer

O(log n)

Answer

O(2n)

Question 4

Which of the following Big O notations represents the most efficient algorithm for a very large input size?

Accepted Answer

O(log n)

Answer

O(n^2)

Answer

O(n log n)

Answer

O(n)

Question 5

What is the time complexity for adding an element to the end of a dynamic array (like a vector in C++) in the amortized case?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n^2)

Question 6

An algorithm with a time complexity of O(1) is said to have:

Accepted Answer

Constant time complexity

Answer

Linear time complexity

Answer

Logarithmic time complexity

Answer

Exponential time complexity

Question 7

Consider the code: for (int i = 1; i < n; i = i * 2) { /* statement */ }. What is its time complexity?

Accepted Answer

O(log n)

Answer

O(n)

Answer

O(n^2)

Answer

O(n log n)