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:

• A. both \( O(N) \) and \( \Omega(N) \)
• B. \( O(N) \) but not \( \Omega(N) \)
• C. \( \Omega(N) \) but not \( O(N) \)
• D. neither \( O(N) \) nor \( \Omega(N) \)

Hint:

For algorithms requiring a single traversal through an array, the time complexity is both ( O(N) ) (upper bound) and ( Omega(N) ) (lower bound).

Answer 1

The Correct Option is A

Step 1: Define the problem. The algorithm compares adjacent elements of the array to check if it is sorted in either ascending or descending order. This requires a single pass through the array. Step 2: Time complexity analysis.
In the worst case, the algorithm must traverse the entire array of size \( N \), making \( N-1 \) comparisons.
Thus, the time complexity is \( O(N) \), as the number of operations is proportional to \( N \).
Since the algorithm always requires \( N-1 \) comparisons, the lower bound is also \( \Omega(N) \). Final Answer: \[ \boxed{\text{both } O(N) \text{ and } \Omega(N)} \]