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 compl

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

Accepted Answer

both O(N) and Ω(N). The algorithm checks each pair of adjacent elements in a single pass through the array, which requires examining all N elements, resulting in a linear time complexity of O(N). Since it must at least look at each element once to determine the order, it also has a lower bound of Ω(N), making the correct option both O(N) and Ω(N).

Solution

Related GATE Technical questions