Skip to content
GATEiit

GATE CSE 2024 Session 1 Q17: Worst-case complexity of a single-pass sortedness check

Question

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

Try it: multiple choice: exactly one correct option

Select one option
Wrong answer costs 1/3 mark in GATE.
Show answer and explanation

Answer: A (official GATE 2024 final answer key)

Concept used: Asymptotic bounds of a worst-case running time.

First step: In the worst case (a sorted array) every adjacent pair is compared: about N−1N - 1 comparisons.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Algorithms PYQs

PracticePractise Algorithms questions →Full paperAll GATE CSE 2024 Session 1 questions →