1

Given $n$ numbers, we want to find the maximum. In order to find the maximum in a minimal amount of comparisons, we define a binary tree s.t. we compare $n'_1=\max(n_1,n_2)$, $n'_2=\max(n_3,n_4)$; $n''_1=\max(n'_1,n'_2)$ and so on.

How many maximum comparisons are needed to find the maximum of those $n$ numbers?

When drawing and trying out on paper, I came up with $n-1$ comparisons, but I'm not able to prove this. Any ideas? It's more or less easy to see if $n$ is divsible by 2.

Darth Geek
  • 12,296
a1337q
  • 379
  • nlogn for comparison based procedure. Essentially, this problem reduces to sorting which can be shown to be $\Omega (nlogn)$ for any comparison based procedure. But, if the numbers are fixed integers in a specific range, with counting sort/radix sort, we can get the complexity down to O(n). – user237393 May 08 '15 at 07:41
  • 2
    But you don't need to sort the numbers to find the maximum. n-1 comparisons suffice. – Martin R May 08 '15 at 07:49
  • Good catch, thought OP wanted the first so many maxima – user237393 May 08 '15 at 07:54
  • This question might be more suitable for cs.stackexchange.com, here is a similar question: http://cs.stackexchange.com/questions/35321/how-many-comparisons-do-we-need-to-find-min-and-max-of-n-numbers. Or perhaps programmers.stackexchange.com ? – Martin R May 08 '15 at 07:57
  • The thing why I posted it to mathematics is because I would like to have an idea of a proof.. – a1337q May 08 '15 at 08:00

1 Answers1

0

It is fairly straight-forward to prove with induction that $k-1$ comparisons are enough to find the maximum of $n_1,\dotsc,n_k$.

  • Clearly we need no comparisons to find the maximum of $n_1$.

  • Consider now the numbers $n_1,\dotsc,n_k$ and assume that we can find the maximum of $k-1$ numbers with $k-2$ comparisons. Then we need only one last comparison because $\max(n_1,\dotsc,n_k) = \max(\max(n_1,\dotsc,n_{k-1}),n_k)$.

On the other hand, this is the best case possible, too: suppose that $n_1$ is the maximum of $n_1,\dotsc,n_k$. To decide that it actually is the maximum you need to compare it with each of $n_2,\dotsc,n_k$, i.e. you need $n-1$ comparisons.

A.P.
  • 9,728