1
What does time complexity measure in an algorithm?
Correct Answer
Number of operations executed
☑ MCQ PRACTICE
Design and Analysis of Algorithms Unit 1
Practice objective questions for quick revision and examination preparation. Try answering each question before revealing the answer.
Design and Analysis of Algorithms - Unit-1
2
Which of the following best describes space complexity?
Correct Answer
The amount of memory an algorithm requires to execute
3
What is the space complexity of an algorithm that creates a new array of size n?
Correct Answer
O(n)
4
What is the time complexity of a binary search algorithm?
Correct Answer
O(log n)
5
What is the purpose of asymptotic notation in algorithm analysis?
Correct Answer
To simplify the comparison of algorithms based on their growth rates
6
Which asymptotic notation represents the worst-case time complexity of an algorithm?
Correct Answer
O(n)
7
Which notation describes an Lower bound on the time complexity of an algorithm?
Correct Answer
Ω(n)
8
What does Θ(n) represent in asymptotic notation?
Correct Answer
Tight bound on the time complexity
9
Which of the following is true about the relationship between O(n) and Ω(n)?
Correct Answer
There's no relationship between O(n) and Ω(n)
10
What is the asymptotic notation for constant time complexity?
Correct Answer
O(1)
11
What is a recurrence relation?
Correct Answer
A mathematical expression that defines a function in terms of its value at smaller inputs
12
Which of the following is a common notation for a recurrence relation?
Correct Answer
R(n) = R(n-1) + R(n-2)
13
What is the base case in a recurrence relation?
Correct Answer
The smallest input value(s) for which the recurrence relation is defined directly
14
Which method is commonly used to solve recurrence relations?
Correct Answer
All of the above
15
What is the solution to the recurrence relation T(n) = 2T(n/2) + n?
Correct Answer
O(n log n)
16
In the Master Theorem, what does "a" represent in the form T(n) = aT(n/b) + f(n)?
Correct Answer
The number of subproblems
17
Which case of the Master Theorem applies when the work done at each level of recursion is asymptotically equal?
Correct Answer
Case 2
18
What is the time complexity of the recurrence relation T(n) = T(n/3) + T(2n/3) + n?
Correct Answer
O(n log n)
19
What is the Master Theorem used for?
Correct Answer
Analyzing algorithmic time complexity
20
What is the Master Theorem based on?
Correct Answer
Divide and conquer strategy
21
What is the time complexity of the recurrence relation T(n) = 4T(n/2) + n^2 using the Master Theorem?
Correct Answer
O(n^2)
22
When applying the Master Theorem, what is compared to determine the complexity?
Correct Answer
The size of the original problem and the size of the subproblems
23
Which case of the Master Theorem applies when the work done at each level of recursion decreases geometrically?
Correct Answer
Case 1
24
What is the time complexity of binary search in the worst-case scenario?
Correct Answer
O(log n)
25
Quick sort is an example of a sorting algorithm based on which strategy?
Correct Answer
Divide and conquer
26
What is the worst-case time complexity of quick sort?
Correct Answer
O(n^2)
27
What is the time complexity of merge sort in all cases?
Correct Answer
O(n log n)
28
Strassen's matrix multiplication is an algorithm that multiplies two matrices using which approach?
Correct Answer
Divide and conquer
29
What is the time complexity of Strassen's matrix multiplication algorithm?
Correct Answer
O(n^log7)