1
GATE CSE 2024 Set 1
MCQ (Single Correct Answer)
+1
-0.33

Given an integer array of size $N$, we want to check if the array is sorted (in either ascending or descending order). An algorithm solves this problem by making a single pass through the array and comparing each element of the array only with its adjacent elements. The worst-case time complexity of this algorithm is

A

both $O(N)$ and $\Omega(N)$

B

$O(N)$ but not $\Omega(N)$

C

$\Omega(N)$ but not $O(N)$

D

neither $O(N)$ nor $\Omega(N)$

2
GATE CSE 2023
MCQ (More than One Correct Answer)
+1
-0

Let $$f$$ and $$g$$ be functions of natural numbers given by $$f(n)=n$$ and $$g(n)=n^2$$. Which of the following statements is/are TRUE?

A
$$f \in O(g)$$
B
$$f \in \Omega (g)$$
C
$$f \in o(g)$$
D
$$f \in \Theta (g)$$
3
GATE CSE 2022
MCQ (Single Correct Answer)
+1
-0.33

Which one of the following statements is TRUE for all positive functions f(n) ?

A
f(n2) = $$\theta$$(f(n)2), when f(n) is a polynomial
B
f(n2) = o(f(n)2)
C
f(n2) = O(f(n)2), when f(n) is an exponential function
D
f(n2) = $$\Omega$$(f(n)2)
4
GATE CSE 2021 Set 1
MCQ (Single Correct Answer)
+1
-0.33

Consider the following three functions.

f1 = 10n, f2 = nlogn, f3 = n√n

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

A
f1 , f2, f3
B
f2, f1, f3
C
f3, f2, f1
D
f2, f3, f1
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP