GATE CS 2024 (Forenoon) — Question 17

AlgorithmsAsymptotic Analysis (O, Omega, Theta Complexities)MCQ1 mark · −1/3 if wrongMedium

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. A
    Both \( O(N) \) and \( \Omega(N) \)
  2. B
    \( O(N) \) but not \( \Omega(N) \)
  3. C
    \( \Omega(N) \) but not \( O(N) \)
  4. D
    Neither \( O(N) \) nor \( \Omega(N) \)
Practise the full 2024-FN paper
Challenge a friend: WhatsApp Telegram
From RENYXERAWhat rank do your marks get?GATE score, likely All-India Rank and qualifying marks for your category.
Practise more on Asymptotic Analysis (O, Omega, Theta Complexities)Timed, in the real exam interface · free to start

A GATE question every morning

One real past-paper question every morning for your branch, answer hidden until you tap. Free on Telegram.

Join
Stuck? Ask in the student group