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

O(2^n)

Answer

O(n squared)

Answer

O(log n)

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

O(V squared)

Answer

O(V log V)

Answer

O(E + 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

Bubble Sort — O(n squared)

Answer

Insertion Sort — O(n squared)

Answer

Selection Sort — O(n squared)

Question 4

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

Accepted Answer

Factorial/Super-exponential

Answer

Polynomial

Answer

Exponential

Answer

Linear

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

O(n)

Answer

O(n log n)

Answer

O(2^n)

Question 6

What is the average time complexity of searching in a hash table?

Accepted Answer

O(1)

Answer

O(n)

Answer

O(log n)

Answer

O(n log n)