How does one explain the non-integral number of comparisons in min-max by divide and conquer?

0
votes

For the naïve way, min-max compares 2n-2 times, where as for the divide and conquer way, it compares (3/2)n-2 times. That is exactly (1/2)n comparison less. How does one explain (1/2) comparison? I am entirely lost (I don't even know if my interpretation is wrong). Please help

1
algorithmdivide-and-conquerminmax
What are you talking about? min-max and divide-and-conquer are methods/algorithms to solve problems, comparisons are not a basic brick of them... - Jean-Baptiste Yunès
The question is not about basic bricks or building blocks, it's actually very straightforward. I guess you misread the question :) - kesarling He-Him
@Jean-BaptisteYunès, And don't forget that the very reason of using divide and conquer to find min-max numbers is to lower the comparisons. Whenever you can't reduce the complexity any further, always reduce the number of comparisons is what I have usually heard - kesarling He-Him
I'm not sure to understand your problem: are you trying to get the min and max element of an array? Or are you talking about the minmax algorithm (theory of games)? - Jean-Baptiste Yunès
@Jean-BaptisteYunès, tutorialspoint.com/design_and_analysis_of_algorithms/… This is what I'm talking about - kesarling He-Him

1 Answers

2
votes

Divide and conquer approach (tournament) gives exactly (3/2)n-2 comparisons when n is power of two (2,4,8,16...). Note in this case (3/2)n-2 is integer.

For other values of n exact number of comparisons is slighly higher (consider simple cases of 4,5,6,7 items)

I think this formula is found using recurrence solving like T(n) -... - in this case usually you cannot expect precise values.

Also pairwise-comparison method exists - it provides (3/2)n-2 comparison operations for even n and (3/2)(n+1)-2 comparison operations for odd n values