An array of n distinct elements is said to be un-sorted if  for every index i such that 2 ≤ i ≤ n − 1

An array of n distinct elements is said to be un-sorted if  for every index i such that 2 ≤ i ≤ n − 1, either A[i] > max{A[i − 1], A[i + 1]}, or A[i] < min{A[i − 1], A[i + 1]}.
What is the time-complexity of the fastest algorithm that takes as input a sorted array A with n distinct elements, and un-sorts A?

(A) O(n log n) but not O(n)
(B) O(n) but not O( √n)
(C) O( √n) but not O(log n)
(D) O(log n) but not O(1)

Answer: B

 pairwise swap will make the sorted array unsorted. Hence, the option (B) is correct. 

For eg - if an array is 1 2 3 4 5 6 7 8
The array will become after a pair wise swap to 2 1 4 3 6 5 8 7. For all i between 2 and n−1, a[i] is either lower, or either greater than their adjacent elements. 

Since, each element is being swapped exactly once. The operation has O(n) time complexity.

2Comments
Shubham Agrawal shubhamagrawal 29 Jan 2018 09:28 am
if we swap only the first pair doesnt that make the array unsorted
so why no O(1)??
Sumit Verma sumitverma 29 Jan 2018 03:41 pm
You need to unsort as per given in the question. It's for every element.