Assignment-2
1. Solve T(n) = 3T(n/4) using substitution method.
Answer: Θ(n^log₄3)
2. Solve T(n) = 4T(n/2) using Master Theorem.
Answer: Θ(n²)
3. Solve T(n) = T(n/3) + T(2n/3) using recurrence tree.
Answer: Θ(n)
4. Solve T(n) = T(n−1) + n and derive tight bound.
Answer: Θ(n²)
5. Solve T(n) = T(n/2) + log n using change of variable.
Answer: Θ(log² n)
6. Solve T(n) = 2T(n/2) + n using recurrence tree and Master Theorem.
Answer: Θ(n log n)
7. Solve T(n) = T(n/3) + T(2n/3) + n using recurrence tree.
Answer: Θ(n log n)
8. Solve T(n) = 2T(n/2) + n log n using extended Master Theorem.
Answer: Θ(n log² n)
9. Solve T(n) = T(n−1) + log n.
Answer: Θ(n log n)
10. Write and solve recurrence for Binary Search.
Answer: Θ(log n)
11. Derive and solve recurrence for Merge Sort.
Answer: Θ(n log n)
12. Solve recurrence for classical large integer multiplication: T(n) = 4T(n/2) + n.
Answer: Θ(n²)
13. Solve Karatsuba multiplication recurrence T(n) = 3T(n/2) + n and solve
1026732*732912 using the same.
Answer: Θ(n^log₂3), 752504203584
14. Form and solve recurrence for finding median of two sorted arrays. Apply the
same for series [2, 5, 8, 12, 16].
Answer: Θ(log n)
15. Solve Strassen’s matrix multiplication recurrence T(n) = 7T(n/2) + n². And solve
a 4*4 matrix using same.
Answer: Θ(n^log₂7)
16. Write and solve recurrence for fast exponentiation also compute x13.
Answer: Θ(log n)
17. Derive recurrence for finding max and min using divide and conquer.
Answer: Θ(n)
18. Solve non-homogeneous recurrence T(n) = 2T(n/4) + √n.
Answer: Θ(√n log n)
19. An algorithm divides problem into 3 subproblems of size n/2 and combines in
linear time. Form recurrence and solve.
Answer: T(n)=3T(n/2)+n, Θ(nlog23)
20. An algorithm divides a problem into 4 subproblems of size n/2 and combines the
results in quadratic time.
Answer: T(n)=4T(n/2)+n2, Θ(n2logn)