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)