GATE CSE 2005 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2005

MCQ (Single Correct Answer)

-0.3

The time complexity of computing the transitive closure of a binary relation on a set of elements is known to be:

O (n)

O (n log n)

O (n^3/2)

O (n³)

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

P₃ is decidable if P₁ is reducible to P₃

P₃ is undecidable if P₃ is reducible to P₂

P₃ is undecidable if P₂ is reducible to P₃

P₃ is decidable if P₃ is reducible to P₂ 's complement

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Suppose T(n) = 2T (n/2) + n, T(0) = T(1) = 1
Which one of the following is FALSE?

T(n) = O(n²)

$$T\left( n \right){\rm{ }} = {\rm{ }}\theta \left( {n{\rm{ }}\,log\,{\rm{ }}n} \right)$$

$$T\left( n \right){\rm{ }} = {\rm{ }}\Omega ({n^2})$$

T(n) = O(n log n)

GATE CSE 2005

MCQ (Single Correct Answer)

-0.6

Suppose there are $$\lceil \log n \rceil$$ sorted lists of $$\left\lfloor {{n \over {\log n}}} \right\rfloor $$ elements each. The time complexity of producing a sorted list of all these elements is :
(Hint : Use a heap data structure)

$$O(n \log \log n)$$

$$\Theta(n \log n)$$

$$\Omega(n \log n)$$

$$\Omega\left(n^{3/2}\right)$$

GATE CSE Papers

All year-wise previous year question papers

2026