MHB Find the second smallest element

[I like Serena]

Could you give me an example? (Thinking)

What example can you think of? (Wasntme)

 

[evinda]

What example can you think of? (Wasntme)

Having the tournament tree for $n$ elements,where can I place the $(n+1)^{th}$ element? (Thinking)

 

[I like Serena]

Having the tournament tree for $n$ elements,where can I place the $(n+1)^{th}$ element? (Thinking)

Two cases.
If $n$ is of the form $2^k$, you'll need another level and do what I showed in my tree.
Or if $n$ is not of the form $2^k$, you can add it to the right of the last leaf. (Tauri)

 

[evinda]

Two cases.
If $n$ is of the form $2^k$, you'll need another level and do what I showed in my tree.
Or if $n$ is not of the form $2^k$, you can add it to the right of the last leaf. (Tauri)

So, if we have $m$ elements and we want to create a tournament tree, doesn't all the $m$ elements have to be firstly at the same level, that is the last one?

Because, if we have $n+1$ elements, we compare the $(n+1)^{th}$ element with the smallest that we found before when we had $n$ elements,and pick one of them, and then we only have $n$ elements at the same level..

 

[I like Serena]

So, if we have $m$ elements and we want to create a tournament tree, doesn't all the $m$ elements have to be firstly at the same level, that is the last one?

No!
That only works if we happen to have a power of 2.
What if we don't? (Wait)

Because, if we have $n+1$ elements, we compare the $(n+1)^{th}$ element with the smallest that we found before when we had $n$ elements,and pick one of them, and then we only have $n$ elements at the same level..

Huh?

We don't have to compare $(n+1)$ with the smallest.
We only have to add it to the tree.
The exact comparisons may change, but the total number of comparisons will be 1 more than it was before. (Wasntme)

 

[evinda]

No!
That only works if we happen to have a power of 2.
What if we don't? (Wait)

So, what do we have to do, when we have $n=11$ ? $11$ is not a power of $2$, neither $n-1=10$ is.. (Worried)

Huh?

We don't have to compare $(n+1)$ with the smallest.
We only have to add it to the three.
The exact comparisons may change, but the total number of comparisons will be 1 more than it was before. (Wasntme)

So, at the binary tree, that you created, don't we have to compare only $9$ with $1$ ? (Sweating)

View attachment 3240

 

[I like Serena]

So, what do we have to do, when we have $n=11$ ? $11$ is not a power of $2$, neither $n-1=10$ is.. (Worried)

Can you create a tree for that? (Wondering)

So, at the binary tree, that you created, don't we have to compare only $9$ with $1$ ? (Sweating)

Not really. We can shuffle the leaves around any way we like. (Dance)

 

[evinda]

Can you create a tree for that? (Wondering)

I thought that it would be like that:

View attachment 3244

So, is it wrong? (Thinking) Do we have to put the first $2^3=8$ elements at the same level and the remaining $11-8=3$ elements at the next level?

Not really. We can shuffle the leaves around any way we like. (Dance)

How could we do it otherwise? (Worried)

 

[evinda]

I have an idea! (Nerd)

Can we prove the sentence, using strong induction? (Wait)

We will show that with at most $ n + \lceil \lg{n}\rceil - 2$ comparisons we can find the smallest and the second smallest element.

The sentence is true for $n=2$ $\checkmark$ .

We suppose that it stands $\forall 2<k<n$.

Now, we distinguish cases:

• If $n=2m$, we split the elements into $m$ pairs , needing $m$ comparisons.
  
  From each comparison, we pick the smallest number.
  
  From the inductive step, we know that we need at most $m + \lceil \lg{m}\rceil - 2$ comparisons, in order to find the smallest and the second smallest element from the remaining numbers, let $d,e$, with $d<e$.
  
  Also, suppose that at the first $m$ comparisons, $d$ was compared with $d'$.
  
  Then, the smallest element of the initial set of numbers is $d$, and the second smallest element is either $e$ or $d'$.
  
  With one more comparison, we can find which of these two elements is smaller.
  
  In total, we needed:
  
  $$m + (m + \lceil \lg{m}\rceil - 2) + 1 = 2m + \lceil \lg{m} + 1\rceil -2 = n + \lceil \lg{n}\rceil - 2$$
  comparisons.
  $$$$
• Similarly, if $n=2m+1$, we split the elements into $m$ pairs and we leave an element alone .
  
  After $m$ comparisons, we have the smallest $m$ elements and the one that we have left alone , and then with $(m+1) + \lceil \lg{(m+1)}\rceil - 2$ comparisons , we find the smallest and the second smallest from the $m+1$ elements.
  
  Finally, with at most one comparison we find the smallest and the second smallest element of the initial set of numbers. In total, we needed
  $$$$
  $$m + (m+1 + \lceil \lg{(m+1)}\rceil - 2) + 1 = 2m+1 + \lceil \lg{(m+1)} + 1\rceil -2 \\ = n+ \lceil \lg { \left ( \frac{2m+2}{2}\right )+1 \rceil}-2=n+ \lceil \lg { (2m+2} ) \rceil-2= n+ \lceil \lg { (n+1} ) \rceil-2$$
  comparisons.

Is it right so far? Also, how can I show that $n+ \lceil \lg { (n+1} ) \rceil-2$ is equal to $n+ \lceil \lg { n} \rceil-2$ ? (Thinking)