# Algorithms-Asymptotic Notation [GATE (Graduate Aptitude Test in Engineering) Computer Science]: Questions 1 - 6 of 6

Access detailed explanations (illustrated with images and videos) to 2122 questions. Access all new questions- tracking exam pattern and syllabus. View the complete topic-wise distribution of questions. Unlimited Access, Unlimited Time, on Unlimited Devices!

View Sample Explanation or View Features.

Rs. 550.00 -OR-

## Question 1

Asymptotic Notation

Appeared in Year: 2014 (UGC-NET)

### Question

Match List-Ⅰ List-Ⅱ▾

Match the following: (December Paper III)

List-Ⅰ (Column I)List-Ⅱ (Column II)
(A)

Matrix chain multiplication

(i)

(B)

All pairs shortest paths

(ii)

(C)

Huffman

(iii)

(D)

Bucket sort

(iv)

### Choices

Choice (4)Response
• (A)
• (B)
• (C)
• (D)

a.

• (i)
• (ii)
• (iv)
• (iii)

b.

• (ii)
• (i)
• (iii)
• (iv)

c.

• (iv)
• (ii)
• (i)
• (iii)

d.

• (i)
• (iv)
• (ii)
• (iii)

## Question 2

Asymptotic Notation

Appeared in Year: 2014 (UGC-NET)

### Question

MCQ▾

Big-O estimates for the factorial function and the logarithm of the factorial function i.e.. and is given by (June paper II)

### Choices

Choice (4)Response

a.

b.

c.

d.

## Question 3

Asymptotic Notation

Appeared in Year: 2014 (UGC-NET)

### Question

MCQ▾

Given the following equalities:

for all fixed and , and .

Which of the following is true? (June paper III)

### Choices

Choice (4)Response

a.

.

b.

.

c.

d.

.

## Question 4

Asymptotic Notation

### Question

MCQ▾

What is the Big-O estimate for the function given below?

### Choices

Choice (4)Response

a.

b.

c.

d.

## Question 5

Asymptotic Notation

Appeared in Year: 2019 (UGC-NET)

### Question

MCQ▾

Give asymptotic upper and lower bound for given below. Assume is constant for .

(December)

### Choices

Choice (4)Response

a.

b.

c.

d.

## Question 6

Asymptotic Notation

Appeared in Year: 2019 (UGC-NET)

### Question

MCQ▾

The following multithreaded algorithm computes transpose of a matrix in parallel: (December)

1. `p Trans (X, Y, N)`
2. `if N =1`
3. `then Y [1, 1] ⇽ X [1, 1]`
4. `else partition X into four (N / 2) × (N/2) submatrices X11, X12, X21, X22`
5. `partition Y into four (N / 2) × (N/2) submatrices Y11, Y12, Y21, Y22`
6. `spawn p Trans (X11, Y11, N/2)`
7. `spawn p Trans (X12, Y12, N/2)`
8. `spawn p Trans (X21, Y21, N/2)`
9. `spawn p Trans (X22, Y22, N/2)`

What is the asymptotic parallelism of the algorithm?

### Choices

Choice (4)Response

a.

b.

c.

d.

Developed by: