The recurrence T(n) = T(n/2) + 1 has a time complexity of: (i) O(n) (i — PYQDeck

PyQdeckBEU PYQ Archive Subjects

Back to the 2024 paper

Module 1: Introduction

20242m

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)$

Search Google Ask AI

Similar questions

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 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 & Analysis of AlgorithmsSolve the recurrence relation T(n) = 2T(n/2) + O(n)20247m Design and Analysis of Algorithms What is the complexity of T(n) = 2T(n/4) + n^2 \log n? (i) \Theta(n^2 \log(\log n)) (ii) \Theta(n^3 \log n) (iii) \Theta(n^2 \log n) (iv) \Theta(n \log n)20232m

PreviousIf an algorithm has time complexity T(n) = 5n^2 + 3n + 7, its asymptotic upper bound is: (i) O(n) (ii) O(n^2) (iii) O(n \log n) (iv) O(n^3)NextWhich strategy solves problems by solving subproblems and combining their solutions? (i) Brute Force (ii) Greedy (iii) Dynamic Programming (iv) Backtracking