GATE CS 2024 Set 1 Q.17: Asymptotic Analysis and Time/Space Complexity

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

both $\text{O}(N)$ and $\Omega(N)$

$\text{O}(N)$ but not $\Omega(N)$

$\Omega(N)$ but not $\text{O}(N)$

neither $\text{O}(N)$ nor $\Omega(N)$

Official answer and solution

Official answer: A
From: Official GATE 2024 answer key

Solution

Determine the number of comparisons made in a single pass when the array is sorted (the worst case for verifying sortedness).

To verify whether an array of size $N$ is sorted in a single pass of adjacent comparisons, the worst case occurs when the array is actually sorted (or when the only out-of-order pair is at the very end of the array). In this worst case, the algorithm must examine all $N$ elements (performing $\Theta(N)$ comparisons). A function in $\Theta(N)$ is both $O(N)$ and $\Omega(N)$ .

Final answer

Option (A)

Common trap

Confusing the best-case time complexity $\Omega(1)$ (early exit on the first few elements) with the lower bound $\Omega(N)$ of the worst-case time complexity function $T_{\text{worst}}(N) = \Theta(N)$ .

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 1 (CS1)
Question: 17 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source