Design and Analysis of Algorithms MCQs with Answers
Practice important Design and Analysis of Algorithms MCQs with answers and explanations.
Multiple Choice Questions
Q41: According to the limit rule, if f(n)/g(n) approaches a constant c (c > 0) as n → ∞, then f(n) ∈ ______.
- A: Θ(g(n))
- B: O(g(n))
- C: Ω(g(n))
- D: None of these
View Answer
A
Q42: If f(n) = 8n^2 + 2n - 3, which of these could serve as a lower bound constant in Θ-notation?
- A: 7
- B: 2
- C: 10
- D: √3
View Answer
A
Q43: Which complexity class denotes algorithms with exponential time complexity?
- A: Θ(n^2)
- B: Θ(2^n)
- C: Θ(log n)
- D: Θ(1)
View Answer
B
Q44: Fill in the blank: Asymptotic notation focuses on how functions behave as ______ becomes large.
- A: n
- B: g(n)
- C: f(n)
- D: c
View Answer
A
Q45: In Θ-notation, which of the following does NOT need to be specified?
- A: Upper bound
- B: Lower bound
- C: Exact function
- D: Both upper and lower bounds
View Answer
C
Q46: Fill in the blank: To prove f(n) ∈ O(g(n)), you need to establish a(n) ______ bound.
- A: asymptotic
- B: upper
- C: lower
- D: exact
View Answer
B
Q47: Which function's growth rate would typically fall into Θ(n log n) class?
- A: Binary search
- B: Merge sort
- C: Linear search
- D: Exponential calculation
View Answer
B
Q48: What is the primary strategy of "Divide and Conquer"?
- A: Breaking problems into parts
- B: Combining results without recursion
- C: Using only one step to solve
- D: Ignoring smaller problems
View Answer
A
Q49: In the "Conquer" step of Divide and Conquer, what is generally done?
- A: Problems are ignored
- B: Problems are combined directly
- C: Each piece is solved recursively
- D: All pieces are re-sorted
View Answer
C
Q50: Which sorting algorithm is used as an example of the Divide and Conquer strategy?
- A: Quick Sort
- B: Bubble Sort
- C: Merge Sort
- D: Selection Sort
View Answer
C