AMCAT Algorithm Complexity 3

Question 1

What is the time complexity of finding the nth Fibonacci number using dynamic programming (memoization)?

Accepted Answer

O(n)

Answer

With memoization, each Fibonacci value is computed once. There are n unique subproblems — O(n) time.

Question 2

What is the time complexity of Dijkstra's shortest-path algorithm using a binary heap priority queue?

Accepted Answer

O(E log V)

Answer

With a binary heap, each edge relaxation is O(log V) and there are E relaxations — O(E log V).

Question 3

Which of the following has the best average-case time complexity for sorting?

Accepted Answer

Merge Sort — O(n log n)

Answer

Merge Sort guarantees O(n log n) average and worst case, which is optimal for comparison-based sorting.

Question 4

An algorithm with O(n!) complexity is described as:

Accepted Answer

Factorial/Super-exponential

Answer

O(n!) is factorial time complexity, which grows faster than exponential O(2^n). It appears in brute-force permutation problems.

Question 5

What is the time complexity of: for(int i=0; i<n; i++) for(int j=i; j<n; j++) { }?

Accepted Answer

O(n squared)

Answer

Total iterations = n + (n-1) + ... + 1 = n(n+1)/2 = O(n^2).

(AMCAT) Aspiring Minds Computer Adaptive Test Practice Test