Back to the 2024 paper
Similar questions
Design & Analysis of AlgorithmsWrite time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method: ``c rec(n) { if (n <= 1) return(1); else { rec(n / 2); for (i = 1; i <= n; i++) printf("algorithm"); } } ``20227mDesign & Analysis of AlgorithmsCalculate the time complexity of the following problem using divide and conquer strategies: (i) T(n) = \sqrt{n} \cdot T(\sqrt{n}) + n, \quad n > 2 (ii) T(n) = T(n-1) + 1/n, \quad n > 120227mDesign and Analysis of Algorithms The recurrence T(n) = T(n/2) + 1 has a time complexity of: (i) O(n) (ii) O(\log n) (iii) O(n \log n) (iv) O(n^2)20242mDesign and Analysis of Algorithms Consider the following recurrence relation: T(n) = 2T(n/2) + n Use the substitution method to find an asymptotic upper bound for the function T(n).20237m
PreviousAnswer the following: (i) Differentiate between best-case, worst-case, and average-case complexity with suitable examples. (ii) Use examples like linear search to demonstrate the differences. (iii) Discuss why worst-case analysis is often preferred in practice.NextWhat is the Master's Theorem? State the general form and the three cases of the theorem. Use it to solve the following recurrence relations: (i) T(n) = 2T(n/2) + n (ii) T(n) = 3T(n/2) + n^2 (iii) T(n) = 2T(n/2) + n/\log n Explain which case applies in each situation.