MHB Find the second smallest element

[evinda]

Hi! (Nerd)

Show that,given a set of numbers $S$,we can count the second smallest element of $S$ with $n+ \lceil \lg n \rceil-2$ comparisons at the worst case.

Hint: Find the smallest element,considering a tournament tree for its finding.

I don't really know how to use the hint.. (Sweating) Could you help me? (Blush)

 

[magneto1]

Build a tournament tree by first pairing the $n$ elements together, and the smaller element of the pair advances to the next round of the tournament. This will yield a binary tree of height $\left\lceil{\log_2 n}\right\rceil$.

Also, the number of comparisons needed to create this tree would be defined by the recurrence $T(n) = T(n/2) + \frac n2$, and $T(1)=0$. because at each round, we do $\frac n2$ comparisons and move onto the next round. That recurrence has a solution of $T(n) = n - 1$.

After $n-1$ comparisons to build the tree, we know the root of the tree (the winner) is the smallest element. All we need now is to go to each depth of the tree and find out the element that the winner beats. There will be $\left\lceil{\log_2 n}\right\rceil$, we can find the minimum of this set with $\left\lceil{\log_2 n}\right\rceil - 1$ comparisons (linear scan).

Total number of comparisons is $n-1 + \left\lceil{\log_2 n}\right\rceil - 1$.

 

[I like Serena]

Hi! (Nerd)

Show that,given a set of numbers $S$,we can count the second smallest element of $S$ with $n+ \lceil \lg n \rceil-2$ comparisons at the worst case.

Hint: Find the smallest element,considering a tournament tree for its finding.

I don't really know how to use the hint.. (Sweating) Could you help me? (Blush)

Hey! (Happy)

Let's pick an example.

Suppose we have the following tournament tree:
View attachment 3136

What is $n$?
What is the number of comparisons to find the winner?
And what is the number of additional comparisons we need to find number 2? (Wondering)

 

[evinda]

Hey! (Happy)

Let's pick an example.

Suppose we have the following tournament tree:
View attachment 3136

What is $n$?

$n=4$,right? (Wasntme)

What is the number of comparisons to find the winner?

And what is the number of additional comparisons we need to find number 2? (Wondering)

Number of comparisons=3
Is it maybe like that:
Number of additional comparisons=Number of comparisons-1=2 ? (Thinking)

 

[I like Serena]

$n=4$,right? (Wasntme)

Right!

Number of comparisons=3

Good!
Can you express that as a relationship with $n$?

Is it maybe like that:
Number of additional comparisons=Number of comparisons-1=2 ? (Thinking)

Sorry, but no.

Perhaps we should look at an example with $n=8$... (Thinking)

 

[evinda]

Good!
Can you express that as a relationship with $n$?

It is equal to $n-1$..

Sorry, but no.

Perhaps we should look at an example with $n=8$... (Thinking)

I created a turnament tree for $n=8$:

View attachment 3140

But..how can I find the number of additional comparisons we need to find number 2? (Thinking)

 

[I like Serena]

It is equal to $n-1$..

Yep!

I created a turnament tree for $n=8$:

But..how can I find the number of additional comparisons we need to find number 2? (Thinking)

Which contenders might be second best? (Wondering)

Starting at the left, could contender 5 be second best?

 

[evinda]

Which contenders might be second best? (Wondering)

Starting at the left, could contender 5 be second best?

No,because $5<7<9$,right? (Thinking)

 

[I like Serena]

No,because $5<7<9$,right? (Thinking)

Correct.
From the position in the tree, you already know that $5$ cannot be second, but $7$ might be.
Which others are there? (Wondering)

 

[evinda]

Correct.
From the position in the tree, you already know that $5$ cannot be second, but $7$ might be.
Which others are there? (Wondering)

The possible numbers that could be second are these: $7,2,6,7$.

Then,these: $7,7$.

And,then,this: $7$.

Right? (Thinking)

 

[I like Serena]

The possible numbers that could be second are these: $7,2,6,7$.

Then,these: $7,7$.

And,then,this: $7$.

Right? (Thinking)

From the tournament tree, we have already had a match between $7$ and $2$, and $7$ came out on top.
So $2$ cannot be second. At best he is third.

We haven't had a match between $6$ and $7$ though. So both are still contenders for second place.

Btw, you have a duplicate $7$ in the bottom right. (Doh)
Was that intentional?
Or should it really be for instance $8$? (Wondering)

 

[evinda]

From the tournament tree, we have already had a match between $7$ and $2$, and $7$ came out on top.
So $2$ cannot be second. At best he is third.

We haven't had a match between $6$ and $7$ though. So both are still contenders for second place.

Btw, you have a duplicate $7$ in the bottom right. (Doh)
Was that intentional?
Or should it really be for instance $8$? (Wondering)

I replaced $7$ by $8$:

View attachment 3145

So,now do we have to find the greatest number,less than $9$,from the right subtree and compare it with $7$?
So,the number of comparisons is $4=\frac{n}{2}$ ,right? (Thinking)

 

[I like Serena]

So,now do we have to find the greatest number,less than $9$,from the right subtree and compare it with $7$?
So,the number of comparisons is $4=\frac{n}{2}$ ,right? (Thinking)

The second best will come out on top everywhere - except when compared with number one.
There are three numbers that are on top, but that lose from number one: $\enclose{circle}7$, $\enclose{circle}6$, and $\enclose{circle}8$.
These are the candidates for second best.

The number of these candidates corresponds to the height of the tree minus 1.
What is the height of a binary tree with $n$ leafs? (Wondering)
Hint: it is not $\frac n 2$.

Now suppose we have $m$ candidates for number two.
Then we can create a new tournament tree, for which we already know that we need $m-1$ comparisons.

 

[evinda]

The second best will come out on top everywhere - except when compared with number one.
There are three numbers that are on top, but that lose from number one: $\enclose{circle}7$, $\enclose{circle}6$, and $\enclose{circle}8$.
These are the candidates for second best.

The number of these candidates corresponds to the height of the tree minus 1.
What is the height of a binary tree with $n$ leafs? (Wondering)
Hint: it is not $\frac n 2$.

Isn't the height of a binary tree with $n$ leafs equal to $\lfloor \lg n\rfloor$ ? Or am I wrong? (Thinking)

But..in our case, $ \lg n-1=\lg 8-1=\lg {2^3}-1=3-1=2$,and there are $3$ candidates..or not? (Sweating)

Now suppose we have $m$ candidates for number two.
Then we can create a new tournament tree, for which we already know that we need $m-1$ comparisons.

So,is it like that? (Thinking)

View attachment 3162

 

[I like Serena]

Isn't the height of a binary tree with $n$ leafs equal to $\lfloor \lg n\rfloor$ ? Or am I wrong? (Thinking)

But..in our case, $ \lg n-1=\lg 8-1=\lg {2^3}-1=3-1=2$,and there are $3$ candidates..or not? (Sweating)

Let's see... if we have $n=1$ leafs, what is the height of the tree?
If we have $n=2$, what is the height of the tree?
If we have $n=4$, what is the height of the tree?
If we have $n=8$, what is the height of the tree?
If we have $n=16$, what is the height of the tree?
If we have $n=15$, what is the height of the tree?
If we have $n=9$, what is the height of the tree? (Wondering)

So,is it like that? (Thinking)

Yep. That's the tree for second best.
So it takes 2 comparisons. (Smile)

 

[evinda]

Let's see... if we have $n=1$ leafs, what is the height of the tree?
If we have $n=2$, what is the height of the tree?
If we have $n=4$, what is the height of the tree?
If we have $n=8$, what is the height of the tree?
If we have $n=16$, what is the height of the tree?
If we have $n=15$, what is the height of the tree?
If we have $n=9$, what is the height of the tree? (Wondering)

If we have $n=1$, height=1.
If we have $n=2$, height=1.
If we have $n=4$, height=2.
If we have $n=8$, height=3.
If we have $n=16$, height=4.
If we have $n=15$ ,height=4.
If we have $n=9$, height=3.

Right? (Thinking)

Yep. That's the tree for second best.
So it takes 2 comparisons. (Smile)

(Nod)

 

[I like Serena]

If we have $n=1$, height=1.

Yep! (Smile)

If we have $n=2$, height=1.

In this case we have 2 leaves and 1 root.

View attachment 3163

That means there are 2 levels.
Or in other words, the height of the tree is 2 instead of 1. (Worried)

 

[evinda]

In this case we have 2 leaves and 1 root.

View attachment 3163

That means there are 2 levels.
Or in other words, the height of the tree is 2 instead of 1. (Worried)

I thought that,if there is just one node,the root node,the height is equal to $0$,if there are $2$ levels of nodes,the height is equal to $1$ and so on. Am I wrong? (Thinking)

 

[I like Serena]

I thought that,if there is just one node,the root node,the height is equal to $0$,if there are $2$ levels of nodes,the height is equal to $1$ and so on. Am I wrong? (Thinking)

I have just looked it up and I see conflicting information.

In binary tree on wiki, the height is the same as the number of levels.

But in tree (data structure) on wiki, the height is the number of levels minus one.

So I don't know! (Doh)
I'll just refer to levels from now on to avoid the confusion.

So with your interpretation, you are (almost) right!Still...

If we have $n=8$, height=3.
If we have $n=9$, height=3.

With $n=8$ leaves we have a full binary tree with 4 levels.
With $n=9$ we need one more level, so we have 5 levels! (Worried)

Can you find the formula for the number of levels based on the number of leaves? (Wondering)

 

[evinda]

I have just looked it up and I see conflicting information.

In binary tree on wiki, the height is the same as the number of levels.

But in tree (data structure) on wiki, the height is the number of levels minus one.

So I don't know! (Doh)
I'll just refer to levels from now on to avoid the confusion.

So with your interpretation, you are (almost) right!Still...With $n=8$ leaves we have a full binary tree with 4 levels.
With $n=9$ we need one more level, so we have 5 levels! (Worried)

So, is it of this form, for $n=8$? (Thinking)

View attachment 3164

If so,why do we need one more level for $n=9$ ? (Thinking)

 

[I like Serena]

So, is it of this form, for $n=4$? (Thinking)

View attachment 3164

If so,why do we need one more level for $n=9$ ? (Thinking)

That tree has $n=5$ leaves...

So it has one level more than a tree with $n=4$ leaves.

 

[evinda]

That tree has $n=5$ leaves...

Oh yes,right! (Blush)

So it has one level more than a tree with $n=4$ leaves.

So, is it like that? Or have I done something wrong? (Thinking)

number of leaves =1, number of levels=2

number of leaves =2, number of levels=2

number of leaves =4, number of levels=3

number of leaves =8, number of levels=4

number of leaves=16, number of levels=5

number of leaves=15, number of levels=5

number of leaves=9, number of levels=5

 

[I like Serena]

So, is it like that? Or have I done something wrong? (Thinking)

Almost!

number of leaves =1, number of levels=2

If we have 1 leaf, there is only 1 node, and only 1 level.

How about a formula? (Wondering)

 

[evinda]

If we have 1 leaf, there is only 1 node, and only 1 level.

So, does the tree have to be complete? (Thinking)

How about a formula? (Wondering)

number of leaves =$n$, number of levels= $\lceil \lg n \rceil+1$

Right? (Thinking)

 

[I like Serena]

So, does the tree have to be complete? (Thinking)

That is the way to set up a tournament tree, so let's do it that way. (Mmm)

number of leaves =$n$, number of levels= $\lceil \lg n \rceil+1$

Right? (Thinking)

Right! (Nod)That brings us to how many candidates we have for second place. (Thinking)
And finally how many comparisons we need in total. (Thinking)

 

[evinda]

That is the way to set up a tournament tree, so let's do it that way. (Mmm)

A ok... So, if at the beggining, $n$ is equal to an odd number,for example, $9$, is it then like that?

View attachment 3170

Right! (Nod)That brings us to how many candidates we have for second place. (Thinking)
And finally how many comparisons we need in total. (Thinking)

So, in order to find the first place, we need $n-1$ comparisons and then, in order to find the second place, we need $\lceil \lg n \rceil+1-1= \lceil \lg n \rceil$ comparisons.

Therefore, we need in total $n+ \lceil \lg n \rceil -1$ comparisons, right? (Thinking)

But..the exercise asks to show that we need $n+ \lceil \lg n \rceil−2$ comparisons...

 

[I like Serena]

A ok... So, if at the beggining, $n$ is equal to an odd number,for example, $9$, is it then like that?

It is not a complete binary tree, but yes, we can also do it like that.

So, in order to find the first place, we need $n-1$ comparisons and then, in order to find the second place, we need $\lceil \lg n \rceil+1-1= \lceil \lg n \rceil$ comparisons.

Therefore, we need in total $n+ \lceil \lg n \rceil -1$ comparisons, right? (Thinking)

But..the exercise asks to show that we need $n+ \lceil \lg n \rceil−2$ comparisons...

Let's do this carefully to avoid any plus-or-minus-one mistakes. (Worried)
Take a look at our tree with $n=8$ leaves.
It has $\lceil \lg n \rceil + 1 = 4$ levels yes?
How many candidates for second place does that make?
Is it the same or is it different? (Wondering)

 

[evinda]

Let's do this carefully to avoid any plus-or-minus-one mistakes. (Worried)
Take a look at our tree with $n=8$ leaves.
It has $\lceil \lg n \rceil + 1 = 4$ levels yes?

(Nod)

How many candidates for second place does that make?
Is it the same or is it different? (Wondering)

There are $\lceil \lg n \rceil=3$ candidates for the second place, right? (Thinking)

 

[I like Serena]

There are $\lceil \lg n \rceil=3$ candidates for the second place, right? (Thinking)

Right! (Smile)

How many comparisons do we need to find number two? (Thinking)

 

[evinda]

Right! (Smile)

How many comparisons do we need to find number two? (Thinking)

We need $\lceil \lg n \rceil-1=2$ comparisons, to find number two, right? (Thinking)

 

[I like Serena]

We need $\lceil \lg n \rceil-1=2$ comparisons, to find number two, right? (Thinking)

Yup!

So...? (Sweating)

 

[evinda]

Yup!

So...? (Sweating)

So,we need $n-1+ \lfloor \lg n \rfloor-1=n+ \lfloor \lg n \rfloor -2$ comparisons,right? (Happy)

So, to show that from a given set of numbers with $n$ elements, we can count the second smallest element with $n+ \lceil lgn \rceil−2$ comparisons, can I show it for $n=8$ and then conclude from that the needed number of comparisons for a general $n$ ? Or do I have to do also something else? (Thinking)

 

[I like Serena]

So,we need $n-1+ \lfloor \lg n \rfloor-1=n+ \lfloor \lg n \rfloor -2$ comparisons,right? (Happy)

So, to show that from a given set of numbers with $n$ elements, we can count the second smallest element with $n+ \lceil lgn \rceil−2$ comparisons, can I show it for $n=8$ and then conclude from that the needed number of comparisons for a general $n$ ? Or do I have to do also something else? (Thinking)

Ah well, I guess you still need to prove it.
How would you prove it? (Wondering)

 

[evinda]

Ah well, I guess you still need to prove it.
How would you prove it? (Wondering)

I don't know, maybe using induction? (Thinking)

 

[I like Serena]

I don't know, maybe using induction? (Thinking)

Sounds good... (Smirk)

 

[evinda]

Sounds good... (Smirk)

For $n=2$,we need one comparison to find the second smallest element.

$$n+ \lceil \lg n \rceil -2=2+\lceil \lg 2 \rceil-2=1 \checkmark $$

Then, we suppose that, when we have $n$ elements, we need $n+ \lceil \lg n \rceil -2$ comparisons to find the second smallest element.

But..what happens if we have $n+1$ elements? Do we have to compare the $(n+1)^{th}$ element with the second smallest, that we found above and pick the smallest of them? (Thinking)
Or can't we verify the formula like that? (Sweating)

 

[I like Serena]

For $n=2$,we need one comparison to find the second smallest element.

$$n+ \lceil \lg n \rceil -2=2+\lceil \lg 2 \rceil-2=1 \checkmark $$

Good! (Smile)

Then, we suppose that, when we have $n$ elements, we need $n+ \lceil \lg n \rceil -2$ comparisons to find the second smallest element.

But..what happens if we have $n+1$ elements? Do we have to compare the $(n+1)^{th}$ element with the second smallest, that we found above and pick the smallest of them? (Thinking)
Or can't we verify the formula like that? (Sweating)

We will have to distinguish two cases for $n+1$.

Let's select a complete binary tree for $n$.
When we add leaf $n+1$, there are 2 possibilities.
Either it fits in the last level, or we need to add a new level to accommodate $n+1$.
What happens in those cases to the number of comparisons for first place, respectively second place? (Wondering)

 

[evinda]

We will have to distinguish two cases for $n+1$.

Let's select a complete binary tree for $n$.
When we add leaf $n+1$, there are 2 possibilities.
Either it fits in the last level, or we need to add a new level to accommodate $n+1$.
What happens in those cases to the number of comparisons for first place, respectively second place? (Wondering)

So, don't we consider the tournament tree, proving that we need $n+ \lceil \lg n\rceil-2$ comparisons, by induction? (Sweating) (Thinking)

 

[I like Serena]

So, don't we consider the tournament tree, proving that we need $n+ \lceil \lg n\rceil-2$ comparisons, by induction? (Sweating) (Thinking)

Yes we do.
What's stopping you? (Worried)

 

[evinda]

Yes we do.
What's stopping you? (Worried)

So, when we have $n$ elements, the tournament tree is of this form:

View attachment 3207

and we suppose that we need $n+ \lceil \lg n \rceil-2$ comparisons, in order to find the second smallest element.

But.. what do we do, when we add the $(n+1)^{th}$ element, to show that in this case we need $n+1+ \lceil \lg{ (n+1) } \rceil-2=n+ \lceil \lg{ (n+1) } \rceil-1$ comparisons, for the finding of the second smallest element? (Thinking) (Sweating)

 

[I like Serena]

So, when we have $n$ elements, the tournament tree is of this form:

and we suppose that we need $n+ \lceil \lg n \rceil-2$ comparisons, in order to find the second smallest element.

But.. what do we do, when we add the $(n+1)^{th}$ element, to show that in this case we need $n+1+ \lceil \lg{ (n+1) } \rceil-2=n+ \lceil \lg{ (n+1) } \rceil-1$ comparisons, for the finding of the second smallest element? (Thinking) (Sweating)

In the first case we have a tournament tree that is not a full binary tree, but only a complete binary tree.

When we add leaf $(n+1)$, we need $1$ more comparison to find first place.

Since the tree was not a full binary tree yet, the number of levels stays the same.
Therefore the (worst case) number of comparisons for second place also stays the same.

Therefore the formula $(n+1) + \lceil \lg{ (n+1) } \rceil - 2$ is satisfied. (Wait)

 

[evinda]

In the first case we have a tournament tree that is not a full binary tree, but only a complete binary tree.

Could you explain it further to me, why the tournament tree above is not a full binary tree, but only a complete binary tree? (Sweating)

 

[I like Serena]

Could you explain it further to me, why the tournament tree above is not a full binary tree, but only a complete binary tree? (Sweating)

This is the first of the 2 cases I'm distinguishing.
Either $n$ is of the form $2^k$ or it is not.

If $n$ is not a power of 2, we can set up a tournament tree that is a complete binary tree, but is not a full binary tree. (Wasntme)

 

[evinda]

This is the first of the 2 cases I'm distinguishing.
Either $n$ is of the form $2^k$ or it is not.

If $n$ is not a power of 2, we can set up a tournament tree that is a complete binary tree, but is not a full binary tree. (Wasntme)

A binary tree is full if each node is either a leaf or possesses exactly two child nodes.

A binary tree with $n$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

Right? (Thinking)

So, if $n$ is not a power of $2$, don't we have then a full binary tree, and not a complete one? (Thinking) Or have I understood it wrong? (Sweating)

 

[I like Serena]

A binary tree is full if each node is either a leaf or possesses exactly two child nodes.

A binary tree with $n$ levels is complete if all levels except possibly the last are completely full, and the last level has all its nodes to the left side.

Right? (Thinking)

Right! (Yes)

So, if $n$ is not a power of $2$, don't we have then a full binary tree, and not a complete one? (Thinking) Or have I understood it wrong? (Sweating)

It's the other way around.

 

[evinda]

It's the other way around.

For $n=9$, we have, for example, this tournament tree, right?

View attachment 3208

Why is it a complete binary tree, but not a full one? (Thinking)

 

[I like Serena]

For $n=9$, we have, for example, this tournament tree, right?

Why is it a complete binary tree, but not a full one? (Thinking)

It is neither, because node $\enclose{circle}9$ is really at level 2 instead of on the last level.

The complete binary tree is:
View attachment 3209
And it's not a full binary tree since the last level is not fully occupied. (Shake)

 

[evinda]

It is neither, because node $\enclose{circle}9$ is really at level 2 instead of on the last level.

The complete binary tree is:
https://www.physicsforums.com/attachments/3209
And it's not a full binary tree since the last level is not fully occupied. (Shake)

So, do we have to compare the $(n+1)^{th}$ element with the smallest, that we found, when we had $n$ elements?
If so, then if it is greater, then we need one comparison, right?

And.. if it is smaller than the smallest that we found, do we need again only one comparison, since the new smaller element gets the position of the previous one? (Thinking)

 

[I like Serena]

So, do we have to compare the $(n+1)^{th}$ element with the smallest, that we found, when we had $n$ elements?
If so, then if it is greater, then we need one comparison, right?

And.. if it is smaller than the smallest that we found, do we need again only one comparison, since the new smaller element gets the position of the previous one? (Thinking)

I may have gone overboard when creating the tree. (Blush)

It's not supposed to be sorted.
It was just easiest to do it that way.

We just need to slide element $(n+1)$ in somewhere so that we still have a complete binary tree.
That is always possible and will take exactly $1$ more comparison to figure out number one.

 

[evinda]

It's not supposed to be sorted.
It was just easiest to do it that way.

We just need to slide element $(n+1)$ in somewhere so that we still have a complete binary tree.
That is always possible and will take exactly $1$ more comparison to figure out number one.

Could you give me an example? (Thinking)