0
$\begingroup$

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(nlogn)$ but not $O(n)$
B.$O(n)$ but not $O(\sqrt{n})$
C.$O(\sqrt{n})$ but not $O(logn)$
D.$O(logn)$ but not $O(1)$
E.$ O(1)$

My approach:
1.Pair wise swapping can be done which will result in $O(n)$
2.Starting from the left every even position from the start will be swapped with the even position from the right
1 2 3 4 5 6 7 8 -- 2 will be swapped with 7 similarly 4 and 5
odd length can be also listed which is taking $n/4$ steps
So i want to confirm whether only $O(n)$ is the max can best algorithm can be achieved or better can be achieved.

$\endgroup$
2
$\begingroup$

I think it's not optimal but here's a lower bound: you have to move at least $\lfloor\frac{n}{3}\rfloor$ elements.

Split $A$ into blocks of $3$: {$A[1],A[2],A[3]$}, {$A[4],A[5],A[6]$}, ...

The claim is you have to move at least one element from each block. Otherwise, assume the block {$A[k],A[k+1],A[k+2]$} is kept unchanged. Since $A$ is sorted, $\min(A[k],A[k+2])<A[k+1]<\max(A[k],A[k+2])$, which violates your constraint. So the problem takes $\Omega(n)$. Combine this with your $O(n)$ approach we get $\Theta(n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.