GATE CSE 2022 | Complexity Analysis and Asymptotic Notations Question 7 | Algorithms

PREVIOUS NEXT

GATE CSE 2022

MCQ (More than One Correct Answer)

-0.67

Consider the following recurrence :

f(1) = 1;

f(2n) = 2f(n) $$-$$ 1, for n $$\ge$$ 1;

f(2n + 1) = 2f(n) + 1, for n $$\ge$$ 1;

Then, which of the following statements is/are TRUE?

f(2ⁿ $$-$$ 1) = 2ⁿ $$-$$ 1

f(2ⁿ) = 1

f(5 . 2ⁿ) = 2^{n + 1} + 1

f(2ⁿ + 1) = 2ⁿ + 1

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