GATE CSE 2021 Set 2 | Complexity Analysis and Asymptotic Notations Question 8 | Algorithms

PREVIOUS NEXT

GATE CSE 2021 Set 2

MCQ (Single Correct Answer)

-0.66

For constants a ≥ 1 and b > 1, consider the following recurrence defined on the non-negative integers :

$$T\left( n \right) = a.T\left( {\frac{n}{b}} \right) + f\left( n \right)$$

Which one of the following options is correct about the recurrence T(n)?

If f(n) is $$\frac{n}{{{{\log }_2}(n)}}$$, then T(n) is θ(log₂(n)).

If f(n) is n log₂(n), then T(n) is θ(n log₂(n)).

If f(n) is O(n^{log_b(a) - ϵ}) for some ϵ > 0, then T(n) is θ(n^logb(a)).

If f(n) is θ(n^logb^(a)), then T(n) is θ(n^log^b^(a))

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Consider the following three functions.

f₁ = 10ⁿ, f₂ = n^logn, f₃ = n^√n

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

f₁ , f₂, f₃

f₂, f₁, f₃

f₃, f₂, f₁

f₂, f₃, f₁

GATE CSE 2021 Set 1

MCQ (Single Correct Answer)

-0.67

Consider the following recurrence relation.

$$T(n) = \left\{ {\begin{array}{*{20}{c}} {T(n/2) + T(2n/5) + 7n \ \ \ if\ n > 0}\\ {1\ \ \ \ \ \ \ if\ n = 0} \end{array}} \right.$$

Which one of the following option is correct?

T(n) = Θ(n log n)

T(n) = Θ(n^5/2)

T(n) = Θ((log n)^5/2)

T(n) = Θ(n)

GATE CSE 2019

MCQ (Single Correct Answer)

-0.67

There are n unsorted arrays: A₁, A₂, ..., A_n. Assume that n is odd. Each of A₁, A₂, ..., A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁, A₂, ..., A_n is

$$O\left( n \right)$$

$$O\left( {n\log n} \right)$$

$$O\left( {{n^2}\log n} \right)$$

$$O\left( {{n^2}} \right)$$

PREVIOUS NEXT