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

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

Worked SolutionAI Assisted

Answer: (ii) O(log n)

Master theorem: a=1,b=2,f=1,n^{log_b a}=1 → case 2 with f=Θ(n^{0}) → Θ(log n).

Similar questions

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 Design and Analysis of Algorithms Apply the Master Theorem to determine the time complexity of the following recurrence relations. (i) T(n) = 4T(n/2) + n^3 (ii) T(n) = T(n/2) + 2^n20235m 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 If 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)20242m

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

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.

Get on Google Play