AMCAT Algorithm Complexity 2

Question 1

What is the time complexity of a loop: for(int i=1; i<=n; i*=2)?

Accepted Answer

O(log n)

Answer

The loop variable doubles each iteration: 1, 2, 4, 8, ... running O(log n) iterations.

Question 2

Which sorting algorithm has O(n log n) time complexity in all cases (best, average, worst)?

Accepted Answer

Merge Sort

Answer

Merge Sort always divides into halves and merges, giving O(n log n) in all cases. QuickSort worst case is O(n^2).

Question 3

The recurrence relation T(n) = T(n-1) + O(1) gives what time complexity?

Accepted Answer

O(n)

Answer

T(n) = T(n-1) + 1 expands to n steps: T(n) = n × O(1) = O(n).

Question 4

What is the space complexity of an iterative binary search?

Accepted Answer

O(1)

Answer

Iterative binary search uses only a few variables (low, high, mid) regardless of input size — O(1) space.

Question 5

If an algorithm takes 2 seconds for n=100 and exhibits O(n squared) complexity, how long for n=1000?

Accepted Answer

200 seconds

Answer

O(n^2): n increases 10x so time increases 100x. 2 × 100 = 200 seconds.

(AMCAT) Aspiring Minds Computer Adaptive Test Practice Test