geek mock 2017 #50

Question

Consider an array consisting of –ve and +ve numbers. What would be the worst time comparisons an algorithm can take in order to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other ?

N-1

N

N+1

(N*(N-1))/2

I'm getting N but the solution says N-1 they are using using first element as pivot

but shouldn't we use 0 as pivot hence N should be the answer

Answer 1

Lets take numbers -2, 1 , 2,3

Now, what they are saying is have 2 partitions, put -2 in one partition and hence, - will be base for comparison.

Now, start comparing.

 

Compare -2 and 1.  Sign is differnt. So put 1 in different partition as 1 doesnt have same sign as -2.

 

So, N-1 comparisons

Comments

They are asking best time complexity on worst case input.

---

Yeah I got it thanks for the explanation I was comparing magnitude while I should be comparing signs