Question

You are given an array (vector) of N integers that is sorted in increasing order. You are asked to create a sorted list of the same integers but in decreasing order. You can use any extra arrays, and creating extra arrays takes O(1) time. The most efficient algorithm to achieve this takes time ______.

Answer 1

Answer:

if you use extra array it will take O(n)

Because you should traverse the whole array and copy it to the second array. Though this is O(n) there is a better solution.

I.e., swap first ,last

second last but one and soon

until you reach half. Now the array is automatically in decreasing order .This takes n/2 because you will traverse only through half. Even though its time is O(n) it is most efficient.

Example for this approach:

1 2 3 4

swap 1 : 4 2 3 1

swap 2: 4 3 2 1

now pointer points to middle element so we will break stop swapping.