Algorithm Analysis Quiz

Which of the following is NOT a characteristic of a good algorithm?

• A) Definiteness

• B) Finiteness

• C) Ambiguity

• D) Input and Output

In asymptotic analysis, which notation is used to describe the upper bound of an algorithm's running time?

• A) Big-O (O)

• B) Omega (Ω)

• C) Theta (Θ)

• D) Small-o (o)

Which of the following measures how the running time of an algorithm increases with the size of the input?

• A) Space complexity

• B) Time complexity

• C) Performance complexity

• D) Computation complexity

What does the time-space trade-off imply in algorithm analysis?

• A) More time can reduce the space required

• B) More space can reduce the time required

• C) Both A and B

• D) None of the above

Which method is NOT used for solving recurrence relations?

• A) Substitution Method

• B) Recursion Tree Method

• C) Divide and Conquer Method

• D) Master’s Theorem

Which of the following is an example of a brute-force algorithm?

• A) QuickSort

• B) Bubble Sort

• C) Dijkstra's Algorithm

• D) Dynamic Programming

Strassen’s Matrix Multiplication reduces the time complexity of matrix multiplication to:

• A) O(n^3)

• B) O(n^2.81)

• C) O(n^2)

• D) O(n log n)

Which of the following problems is NOT typically solved using a Greedy Algorithm?

• A) Huffman Coding

• B) 0/1 Knapsack Problem

• C) Prim’s Algorithm

• D) Kruskal’s Algorithm

Which algorithm uses dynamic programming to solve the "All Pairs Shortest Path" problem?

• A) Dijkstra's Algorithm

• B) Bellman-Ford Algorithm

• C) Floyd-Warshall Algorithm

• D) Kruskal’s Algorithm

The time complexity of the Matrix Chain Multiplication problem using dynamic programming is:

• A) O(n^2)

• B) O(n^3)

• C) O(n log n)

• D) O(2^n)