Write time function and calculate the time complexity, space complexit

Back to the 2022 paper

Module 1: Introduction and Complexity Analysis

20227m

Write time function and calculate the time complexity, space complexity and number of function calls of the following pseudocode using substitution method:

rec(n) {
    if (n <= 1) return(1);
    else {
        rec(n / 2);
        for (i = 1; i <= n; i++)
            printf("algorithm");
    }
}

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 Which of the following best describes space complexity? (i) Time taken by the algorithm (ii) Memory required to run an algorithm (iii) Number of recursive calls (iv) Number of loops used20242m Design and Analysis of Algorithms Define time complexity and space complexity. Write an algorithm for adding n natural numbers and find the space required by that algorithm.20257m Design & Analysis of AlgorithmsIn the following C++ function, let n >= m. ``cpp int gcd(int n, int m) { if (n % m == 0) return m; if (n < m) swap(n, m); while (m > 0) { n = n % m; swap(n, m); } return n; } `` What is the time complexity of the above function assuming n > m? - (i) \Theta(\log n) - (ii) \Omega(n) - (iii) \Theta(\log \log n) - (iv) \Theta(\sqrt{n})20192m

PreviousCalculate 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 NextExplain the working of merge sort algorithm with an example. Give the complexity calculation of merge sort.