DAA UNIT-I OBJECTIVE QUESTIONS
1. What does time complexity measure in an algorithm?
A . Number of operations executed
B . Amount of memory used
C . Number of lines of code
D . Input size
2. What is the time complexity of a binary search algorithm?
A . O(1)
B . O(n)
C . O(log n)
D . O(n^2)
3. What is the purpose of asymptotic notation in algorithm analysis?
A . To precisely measure the exact number of operations in an algorithm
B . To provide a rough estimate of algorithmic performance
C . To compare algorithms based on their exact execution times
D . To simplify the comparison of algorithms based on their growth rates
6. Which asymptotic notation represents the worst-case time complexity of an algorithm?
A . Θ(n) B . O(n)
C . Ω(n) D . All of the above
7. Which notation describes an Lower bound on the time complexity of an algorithm?
A . O(n) B . Ω(n)
C . Θ(n) D . All of the above
8. What does Θ(n) represent in asymptotic notation?
A . Best-case time complexity
B . Average-case time complexity
C . Tight bound on the time complexity
D . Worst-case time complexity
11.Which of the following is true about the relationship between O(n) and Ω(n)?
A . O(n) is always greater than Ω(n)
B . Ω(n) is always greater than O(n)
C . O(n) and Ω(n) are equal
D . There`s no relationship between O(n) and Ω(n)
10. What is the asymptotic notation for constant time complexity?
A . O(1) B . O(n)
C . O(log n) D . O(n^2)
11. What is a recurrence relation?
A . A relation between two variables that recurs infinitely
B . A relation between two functions that recurs infinitely
C . A mathematical expression that defines a function in terms of its value at smaller inputs
D . A mathematical expression that defines a function in terms of its value at larger inputs
12. Which of the following is a common notation for a recurrence relation?
A . R(n) = R(n-1) + R(n-2) B . F(n) = F(n+1) - F(n-1)
C . P(n) = P(n^2) D . Q(n) = 2 * Q(n/2)
13. What is the base case in a recurrence relation?
A . The case where the recurrence relation is true for all values of n
B . The case where the recurrence relation is true for some specific value of n
C . The smallest input value(s) for which the recurrence relation is defined directly
D . The largest input value(s) for which the recurrence relation is defined directly
14. Which method is commonly used to solve recurrence relations?
A . Iterative method
B . Dynamic programming
C . Master theorem
D . All of the above
15. What is the solution to the recurrence relation T(n) = 2T(n/2) + n?
A . O(n) B . O(n log n)
C . O(n^2) D . O(2^n)
16. In the Master Theorem, what does "a" represent in the form T(n) = aT(n/
A . The number of subproblems
B . The ratio of subproblem size to original problem size
C . The coefficient of the leading term in the recurrence relation
D . The base case value
17. What is the time complexity of the recurrence relation T(n) = T(n/3) + T(2n/3) + n?
A . O(n) B . O(n log n)
C . O(n^2) D . O(n^3)
19. What is the Master Theorem used for?
A . Solving differential equations
B . Solving recurrence relations
C . Analyzing algorithmic time complexity
D . Finding prime numbers
20. What is the Master Theorem based on?
A . Divide and conquer strategy
B . Dynamic programming
C . Linear algebra
D . Graph theory
21. What is the time complexity of the recurrence relation T(n) = 4T(n/2) + n^2 using the
Master Theorem?
A . O(n) B . O(n log n)
C . O(n^2) D . O(n^2 log n)
22. When applying the Master Theorem, what is compared to determine the complexity?
A . The number of subproblems and the size of each subproblem
B . The size of the original problem and the size of the subproblems
C . The number of recursive calls and the base case value
D . The coefficients of the leading terms in the recurrence relation
23. What is the time complexity of binary search in the worst-case scenario?
A . O(1) B . O(log n)
C . O(n) D . O(n^2)
24. Quick sort is an example of a sorting algorithm based on which strategy?
A . Dynamic programming
B . Greedy approach
C . Divide and conquer
D . Backtracking
25. What is the worst-case time complexity of quick sort?
A . O(n) B . O(n log n)
C . O(n^2) D . O(log n)
26. What is the time complexity of merge sort in all cases?
A . O(n) B . O(n log n)
C . O(n^2) D . O(log n)
27. Strassen`s matrix multiplication is an algorithm that multiplies two matrices using which
approach?
A . Brute force
B . Greedy approach
C . Dynamic programming
D . Divide and conquer
28. What is the time complexity of Strassen`s matrix multiplication algorithm?
A . O(n) B . O(n log n)
C . O(n^2) D . O(n^log7)
29. What is the technique called in which it does not require extra memory for carrying out
the sorting procedure?
A. Stable B. Unstable
C. In-place D. In-partition
30. What is the time complexity of the following code snippet in C++?
void solve() {
string s = "scaler";
int n = s.size();
for(int i = 0; i < n; i++) {
s = s + s[i];
}
cout << s << endl;
}
A. O(n) C. O(n^2)
B. O(1) D. O(log n)
