MadeEasy

Question

An array is said to be random if for every index i such that   1<=i<=n-2 (array start with 0) every 2nd element from start is greater than from its left and right adjacent elements.if input is almost sorted what is time complexity to get random Array.

A.O(n)

B.O(logn)

C.O(nlogn)

D.O(n2)

What is mean by “Almost sorted“ what is its significance here.

 

Comments

but that is not possible according to question

right?

---

@Prateek Raghuvanshi

check this question https://gateoverflow.in/95699/tifr2017-b-7

almost same type

right?

---

@ srestha ,ma'am ,yeah both are almost same type  but in that problem array is already given as sorted but in this question array is almost sorted so we have to sort first using insertion sort and also in this question asking only for every 2nd element follow the given property so we have to swap only one element at every 2nd element.