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

Big O notation is used to describe the upper bound of an algorithm's running time or space requirements in the worst-case scenario. It characterizes how the performance of an algorithm scales as the input size grows.

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

Binary search works by repeatedly dividing the search interval in half. This logarithmic behavior makes it highly efficient for searching in large, sorted datasets, as the number of comparisons grows very slowly with the input size 'n'.

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

For each of the 'n' iterations of the outer loop, the inner loop performs 'n' iterations. This results in a total of n * n = n^2 operations, leading to a quadratic time complexity.

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

An algorithm with O(log n) complexity is the most efficient among the given options because its execution time grows the slowest as the input size 'n' increases. Logarithmic time is significantly better than linear, log-linear, or quadratic time for large inputs.

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

While a single add operation might occasionally take O(n) time if the array needs to be resized, these expensive operations are infrequent. When averaged over a long sequence of additions, the time complexity per operation is constant, or O(1) amortized.

(AMCAT) Aspiring Minds Computer Adaptive Test Practice Test

(AMCAT) Aspiring Minds Computer Adaptive Test Practice Test

FREE AMCAT Algorithm Complexity Questions and Answers