GATE CSE 2003 | GATE CSE Year Wise Previous Years Questions

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is

$$\Theta \,(1)$$

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

$$\Theta \,(n)$$

$$\Theta \,({n^2})$$

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

Consider the following three claims
I. (n + k)^m = $$\Theta \,({n^m})$$ where k and m are constants
II. 2ⁿ⁺¹ = O(2ⁿ)
III. 2²ⁿ = O(2²ⁿ)
Which of those claims are correct?

I and II

I and III

II and III

I, II and III

GATE CSE 2003

MCQ (Single Correct Answer)

-0.3

In a heap with n elements with the smallest element at the root, the 7^th smallest element can be found in time

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

$$\Theta (n)$$

$$\Theta(\log n)$$

$$\Theta(1)$$

GATE CSE 2003

MCQ (Single Correct Answer)

-0.6

The cube root of a natural number n is defined as the largest natural number m such that $${m^3} \le n$$. The complexity of computing the cube root of n (n is represented in binary notation) is

O(n) but not O(n^0.5)

O(n^0.5) but not O((log n)^k) for any constant k > 0

O((log n)^k) for some constant k > 0, but not O((log log n)^m) for any constant m > 0

O((log log n)^k) for some constant k > 0.5, but not O((log log n)^0.5)

GATE CSE Papers

2024