##### 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 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 29 Jan 2018 03:41 pm
You need to unsort as per given in the question. It's for every element.