This set covers the analysis side of Algorithms: asymptotic notation, growth rates, loop complexity, recurrences solved by the Master theorem and recursion trees, and classic divide and conquer algorithms. It helps with GATE preparation, university DAA exams and coding interview rounds, and each answer explains the reasoning step by step.
How to practise: read each question and tap the option you think is correct. You will see right away whether you got it, along with a short explanation, and your score is tracked at the bottom of the screen. This set has 18 questions.
Topics covered in this set
- Big-O, Omega and Theta notation
- Comparing growth rates
- Time complexity of loops
- Master theorem and recursion trees
- Binary search, merge sort and quick sort
- Strassen and closest pair
Algorithms MCQs with answers and explanations
Q1. If f(n) = 3n^2 + 10n log n + 50, then f(n) is:
a) Θ(n log n)
b) Θ(n^2)
c) Θ(n^2 log n)
d) Θ(n^3)
Q2. The statement f(n) = Ω(g(n)) means:
a) There exist constants c > 0 and n0 such that f(n) <= c*g(n) for all n >= n0
b) f(n) and g(n) are equal for all large n
c) f(n)/g(n) tends to 0 as n tends to infinity
d) There exist constants c > 0 and n0 such that f(n) >= c*g(n) for all n >= n0
Q3. Which option lists the functions in increasing order of growth rate?
a) log n < sqrt(n) < n log n < n^2 < 2^n < n!
b) sqrt(n) < log n < n log n < n^2 < 2^n < n!
c) log n < sqrt(n) < n^2 < n log n < 2^n < n!
d) log n < sqrt(n) < n log n < n^2 < n! < 2^n
Q4. Which of the following statements is FALSE?
a) 2^(n+1) is O(2^n)
b) log(n!) is Θ(n log n)
c) 2^(2n) is O(2^n)
d) n^100 is O(1.01^n)
Q5. What is the time complexity of the following code fragment?
for (i = 1; i < n; i = i * 2)
for (j = 0; j < n; j++)
count++;
a) Θ(n log n)
b) Θ(n^2)
c) Θ(n)
d) Θ((log n)^2)
Q6. What is the value of count after the following code runs with n = 10 (count starts at 0)?
count = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= i; j++)
count++;
a) 45
b) 55
c) 100
d) 110
Q7. What is the time complexity of the following code fragment?
for (i = n; i > 0; i = i / 2)
for (j = 0; j < i; j++)
count++;
a) Θ(n log n)
b) Θ(log n)
c) Θ(n^2)
d) Θ(n)
Q8. What is the time complexity of the following loop?
for (i = 1; i * i <= n; i++)
count++;
a) Θ(log n)
b) Θ(n)
c) Θ(sqrt(n))
d) Θ(log log n)
Q9. In the worst case, how many array elements does binary search examine in a sorted array of 1000 elements?
a) 9
b) 10
c) 11
d) 500
Q10. Which statement about standard (top-down) merge sort on an array is correct?
a) It takes Θ(n log n) time in best, average and worst case and needs Θ(n) auxiliary space
b) It takes Θ(n) time when the array is already sorted
c) Its worst case is Θ(n^2) like quick sort
d) It is an in-place algorithm needing only O(1) extra space
Q11. Quick sort that always picks the last element as pivot is run on an already sorted array of n distinct elements. Its running time is:
a) Θ(n)
b) Θ(n log n)
c) Θ(log n)
d) Θ(n^2)
Q12. Using the Master theorem, the solution of T(n) = 4T(n/2) + n is:
a) Θ(n log n)
b) Θ(n)
c) Θ(n^2)
d) Θ(n^2 log n)
Q13. Using the Master theorem, the solution of T(n) = 3T(n/4) + n^2 is:
a) Θ(n^2)
b) Θ(n^0.79)
c) Θ(n^2 log n)
d) Θ(n log n)
Q14. The recurrence T(n) = T(n - 1) + n with T(1) = 1 solves to:
a) Θ(n)
b) Θ(n log n)
c) Θ(2^n)
d) Θ(n^2)
Q15. What is the solution of T(n) = 2T(n/2) + n log n?
a) Θ(n log n)
b) Θ(n (log n)^2)
c) Θ(n^2)
d) Θ(n^1.5)
Q16. Using a recursion tree, the recurrence T(n) = T(n/3) + T(2n/3) + n solves to:
a) Θ(n)
b) Θ(n^2)
c) Θ(n log n)
d) Θ(n log log n)
Q17. Strassen's matrix multiplication uses how many recursive multiplications of half-size matrices, and what is its time complexity?
a) 8 multiplications, Θ(n^3)
b) 7 multiplications, Θ(n^2)
c) 8 multiplications, Θ(n^2.81)
d) 7 multiplications, Θ(n^(log2 7)), about Θ(n^2.81)
Q18. The divide and conquer closest pair of points algorithm achieves O(n log n) time mainly because:
a) In the middle strip, each point needs to be compared with only a constant number of following points in y-sorted order
b) It compares every pair of points inside the strip
c) It uses hashing to find neighbours in O(1) time
d) The points are always uniformly distributed
Quick revision notes
- Growth order: 1 < log n < sqrt(n) < n < n log n < n^2 < 2^n < n! < n^n.
- Doubling or halving loop variable -> log n iterations; i*i <= n -> sqrt(n) iterations.
- Geometric inner loops n + n/2 + n/4 + ... sum to Θ(n).
- Master theorem compares f(n) with n^(log_b a): smaller -> n^(log_b a); equal -> times log n; larger (with regularity) -> f(n).
- T(n) = T(n-1) + n -> Θ(n^2); T(n) = T(n-1) + 1 -> Θ(n); T(n) = 2T(n-1) + 1 -> Θ(2^n).
- Binary search worst case: floor(log2 n) + 1 probes, Θ(log n).
- Merge sort Θ(n log n) always with Θ(n) extra space; quick sort Θ(n log n) best/average, Θ(n^2) worst.
- Strassen Θ(n^2.81); closest pair of points O(n log n).
Frequently asked questions
What is the difference between Big-O and Big-Theta?
Big-O gives only an upper bound, so an algorithm that is Θ(n) is also O(n^2). Big-Theta gives a tight bound, meaning the function is bounded both above and below by constant multiples of the same function.
When can the Master theorem not be used?
It applies only to recurrences of the form T(n) = aT(n/b) + f(n) with a >= 1 and b > 1. It cannot be used when the size decreases by subtraction (like T(n - 1)), when subproblems have unequal sizes, or when f(n) falls in the gaps between the cases; use substitution or a recursion tree there.
Why is quick sort often faster than merge sort in practice despite its Θ(n^2) worst case?
Quick sort sorts in place, has small constant factors and good cache behaviour. With a random or median-of-three pivot the worst case becomes very unlikely, so its expected Θ(n log n) time usually beats merge sort.
Comments
Post a Comment