GATE CSE 2021 Set 1 | Complexity Analysis and Asymptotic Notations Question 14 | Algorithms

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

GATE CSE 2016 Set 2

Numerical

-0

The given diagram shows the flowchart for a recursive function $$A(n).$$ Assume that all statements, except for the recursive calls, have $$O(1)$$ time complexity. If the worst case time complexity of this function is $$O\left( {{n^\alpha }} \right),$$ then the least possible value (accurate up to two decimal positions) of $$\alpha $$ is ____________ . GATE CSE 2016 Set 2 Algorithms - Complexity Analysis and Asymptotic Notations Question 18 English

GATE CSE 2016 Set 2 Algorithms - Complexity Analysis and Asymptotic Notations Question 18 English

Your input ____

GATE CSE 2015 Set 1

MCQ (Single Correct Answer)

-0.6

Consider the following C function.

int fun1 (int n) { 
     int i, j, k, p, q = 0; 
     for (i = 1; i < n; ++i) 
     {
        p = 0; 
       for (j = n; j > 1; j = j/2) 
           ++p;  
       for (k = 1; k < p; k = k * 2) 
           ++q;
     } 
     return q;
}

Which one of the following most closely approximates the return value of the function fun1?

$$n^3$$

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

$$n\log n$$

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

PREVIOUS NEXT