GATE 2021 CS (CS1) – Question 40
Algorithms · Asymptotic Analysis and Time/Space Complexity · 2 marks · Multiple choice
Consider the following recurrence relation.
$T(n) = T(n/2) + T(2n/5) + 7n$ if $n>0$; $T(n)=1$ if $n=0$.
Which one of the following options is correct?
- $T(n) = \Theta(n^{5/2})$
- $T(n) = \Theta(n \log n)$
- $T(n) = \Theta(n)$
- $T(n) = \Theta((\log n)^{5/2})$
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $T(n) = \Theta(n)$
Explanation
Subproblem sizes sum to n/2 + 2n/5 = 9n/10 < n, so the work per level shrinks geometrically. The root's 7n dominates, giving $\Theta(n)$.
More Asymptotic Analysis and Time/Space Complexity questions
- GATE 2020 CS Q12 – For parameters a and b, both of which are (1), T(n)=T(n1/a)+1, and T(b)=1. Then T(n) is
- GATE 2019 CS Q47 – There are n unsorted arrays: A 1,A 2,,A n. Assume that n is odd. Each of A 1,A 2,,A n…
- GATE 2015 CS (CS1) Q60 – An algorithm performs ( N)1/2 find operations, N insert operations, ( N)1/2 delete…
- GATE 2015 CS (CS1) Q64 – Consider the following C function. Which one of the following most closely approximates…
- GATE 2017 CS (CS1) Q14 – Consider the following functions from positive integers to real numbers: 10, n, n, 2 n,…
- GATE 2014 CS (CS1) Q48 – A polynomial-time algorithm correctly computing the largest clique of any graph is…
All Asymptotic Analysis and Time/Space Complexity questions →