GATE CSE 2024 | Set 1 | Question: 7

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 $\mathrm{O}(N)$ and $\Omega(N)$
• B. $\mathrm{O}(N)$ but $\operatorname{not} \Omega(N)$
• C. $\Omega(N)$ but not $\mathrm{O}(N)$ 
• D. neither $\mathrm{O}(N)$ nor $\Omega(N)$

Comments

after go discussions I got to understand the real meaning of this question.

Lost my marks.

Answer 1

The objective of the algorithm is to check whether the array is sorted or not, and it does so by making a single pass through the array.

For this the worst case will be when the array is already sorted.

So, for this worst case, the algorithm has to traverse the whole array and in doing so it will take $O(n)$ time when specified in $O(.)$ notation or $\Omega(n)$ time when specified in $\Omega(.)$ notation.

Answer - A

Comments

for 1st input: the worst case is when we want to check if the array is sorted in ascending order or not as 1 will be checked with 2, as 1 is smaller therefore we will move to 2 and then 2 will be compared with 3 and so on. Therefore the time complexity as scanning the whole array will give bigOh(n) time.

for 2nd input: the worst case will be when we will check for descending order.

for 3rd input: worst case will be bigOh(n) as the whole array elements need to be compared to tell if array is sorted in descending order or not.

for 4th input: worst case is "constant" as only two comparison is needed whether array is in ascending and one comparison is needed for descending order. 

But could you please provide me how the algorithm will work if.

the array is : 1, 1/2, 2/4, 4/8, 6/12.

and I need to check if the array is in descending order or not.

and my stability order is 1/2, 2/4, 4/8, 6/12.

---

We are not supposed to sort the array, we have to only return True or False. Then from where the question of stability comes.

Moreover, the usage of "for input x the worst case will be ..." is wrong.

Bear in mind we have algorithm like -

bool checkSorted(int A[ ]) :

    if (A[1] > A[0]):

        for i in range(2, len(A)):

             if (A[i] < A[i-1]):

                  return False

         return True

    if (A[1] < A[0]):

        for i in range(2, len(A)):

             if (A[i] > A[i-1]):

                  return False

        return True

Here, I have assumed all elements in array are distinct. But algorithm can be easily modified to take care even if elements are not distinct.

As per given description, we don't ask "check if A is sorted in ascending order", we don't ask "check if A is sorted in descending order". We only ask "check if A is sorted", we return True if A is sorted in ascending order, we return True if A is sorted in descending order and we return False if A is neither in ascending order nor in descending order.

---

Alright you said, "check if A is sorted".

Let's say array is: 1,2,3,4,5,6,7

And I want to check if array is sorted or not. 

For checking descending order its the best case as only one comparison is required. But for checking ascending order we need to traverse the entire array (worst case). Right?

Therefore the time complexity is theta(n) implying option a as the answer.

I misjudge the stability part. Alright all clear now. Thanks for the explanation.