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 Ο(𝑁) and Ω(𝑁)

B.

Ο(𝑁) but not Ω(𝑁)

C.

Ω(𝑁) but not Ο(𝑁)

D.

neither Ο(𝑁) nor Ω(𝑁)

Solution:

The given algorithm makes a single pass through the array, comparing each element with its adjacent elements to determine if the array is sorted in either ascending or descending order. 

  • In either the Best-Case or Worst-Case scenario, the algorithm would only need to perform (N-1) comparisons to verify that each element is in the correct order or not to its adjacent element, resulting in a time complexity of Ο(N) or Ω(N).

So, the correct option is A: both Ο(N) and Ω(N)