Redirected
retagged by
2,583 views
16 votes
16 votes

An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $ 2 \leq i \leq n-1$, either $A[i] > \text{max} \{A [i-1], A[i+1]\}$, or $A[i] < \text{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$?

  1. $O(n \: \log \: n)$ but not $O(n)$
  2. $O(n)$ but not $O(\sqrt{n})$
  3. $O(\sqrt{n})$ but not $O(\log n)$
  4. $O(\log n)$ but not $O(1)$
  5. $O(1)$
retagged by

2 Answers

Best answer
19 votes
19 votes

A 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.

edited by
1 votes
1 votes
Another way ..
Taking first index as 1
At odd positions, put elements in ascending order
And at even positions, put elements in descending order.
For Example,
Consider array : 1 2 3 4 5 6 7 8
Unsorted : 1 8 2 7 3 6 4 5
As there are n moves, O(n) Complexity
Answer:

Related questions