The GATE Grind

GATE 2024 CS (CS1) – Question 17

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

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

  1. both $O(N)$ and $\Omega(N)$
  2. $O(N)$ but not $\Omega(N)$
  3. $\Omega(N)$ but not $O(N)$
  4. neither $O(N)$ nor $\Omega(N)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) both $O(N)$ and $\Omega(N)$

Explanation

A single pass with adjacent comparisons takes exactly linear worst-case time, so the worst-case complexity is Θ(N), i.e., both O(N) and Ω(N).