Given an integer array of size N, we want to check if the array is sorted (in…
2024
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 Ω(𝑁)
Attempted by 142 students.
Show answer & explanation
Correct answer: A
Key insight: a single-pass algorithm compares adjacent elements and performs about N-1 comparisons.
Upper bound (O(N)): The algorithm does one pass and makes ≈N-1 adjacent comparisons, so the worst-case time grows linearly with N.
Lower bound (Ω(N)): To be certain an arbitrary array is sorted, an algorithm must examine each element (or each adjacent relation) at least once; therefore no algorithm can always do it in o(N) time.
Conclusion: Both O(N) and Ω(N) hold, so the running time is Θ(N).
A video solution is available for this question — log in and enroll to watch it.