Free AMCAT Algorithm Complexity Questions and Answers 1 — Questions and Answers
Question 1: What does Big O notation represent?
- The exact execution time of an algorithm.
- The best-case time complexity of an algorithm.
- The worst-case time complexity or upper bound of an algorithm's growth rate. (Correct answer)
- The amount of memory an algorithm uses.
Correct answer: The worst-case time complexity or upper bound of an algorithm's growth rate.
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'?
- O(n)
- O(n^2)
- O(log n) (Correct answer)
- O(1)
Correct answer: O(log n)
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:
- O(n)
- O(log n)
- O(n^2) (Correct answer)
- O(2n)
Correct answer: O(n^2)
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?
- O(n^2)
- O(n log n)
- O(n)
- O(log n) (Correct answer)
Correct answer: O(log n)
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?
- O(n)
- O(log n)
- O(1) (Correct answer)
- O(n^2)
Correct answer: O(1)
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.
Question 6: An algorithm with a time complexity of O(1) is said to have:
- Linear time complexity
- Constant time complexity (Correct answer)
- Logarithmic time complexity
- Exponential time complexity
Correct answer: Constant time complexity
O(1) signifies constant time complexity. This means the algorithm takes the same amount of time to execute, regardless of the size of the input data. Accessing an array element by its index is a classic example.
Question 7: Consider the code: for (int i = 1; i < n; i = i * 2) { /* statement */ }. What is its time complexity?
- O(n)
- O(n^2)
- O(log n) (Correct answer)
- O(n log n)
Correct answer: O(log n)
In this loop, the iterator 'i' is doubled in each step (1, 2, 4, 8, ...). The loop stops when 'i' reaches 'n'. This pattern of repeated multiplication means the number of iterations is proportional to the logarithm (base 2) of n, resulting in O(log n) complexity.
Free AMCAT Algorithm Complexity Questions and Answers 1
What does Big O notation represent?