Calculate the time complexity of the following problem using divide an — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2022 paper

Module 1: Introduction and Complexity Analysis

20227m

Calculate 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 > 1$

Search Google Ask AI

Similar questions

Design and Analysis of Algorithms Suppose the number of basic operations in an algorithm is defined as: T(n) = T(n-1) + n, with T(1) = 1. Solve this recurrence using the substitution method and determine the time complexity.20247m Design 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)20242m Design & Analysis of AlgorithmsState Master's theorem and find the time complexity for the following recurrence: T(n) = 2T(n^{1/2}) + \log n20237m Design and Analysis of Algorithms State master's theorem and find the time complexity for the following recurrence: T(n) = 2T(n^{1/2}) + \log n20227m

PreviousThe choice of polynomial class has led to the development of an extensive theory called: - (i) computational complexity - (ii) time complexity - (iii) problem complexity - (iv) decision complexity NextWrite 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"); } } ``