Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# I'm facing a question with comparison networks. Find second and third min.

Posted on 2014-03-23
Medium Priority
385 Views
a. prove that depth of a comparison network that will find values of seond and third minimum is Omega(lg n).
b. build such a network.

I need a hand here.

http://en.wikipedia.org/wiki/File:Six-wire-bubble-sorting-network.svg
0
Question by:aboo_s
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• 6
• 3

LVL 37

Accepted Solution

TommySzalapski earned 900 total points
ID: 39949332
Could you do it for the first minimum?
Do that and then remember that Omega(3 lg n) = Omega(lg n)
0

LVL 10

Author Comment

ID: 39949460
And why is finding the first minimum is Omega(n) in network depth?
You need only n/2 comparators for that.
0

LVL 84

Assisted Solution

ozo earned 600 total points
ID: 39949464
Omega(n) = Omega(n/2) but the depth of a comparison network for the first minimum is Omega(lg n)
0

LVL 10

Author Comment

ID: 39949613
ozo:
I know that the depth is Omega(lg n), I'm asked to prove that. And build such a network.
0

LVL 10

Author Comment

ID: 39949616
If anybody likes to hear it, I'll be more than happy.
0

LVL 84

Expert Comment

ID: 39949626
Can you find an Omega(lg n) depth network for the first minimum?
0

LVL 10

Author Comment

ID: 39949645
Yes, that's what I have found.  Attached is an example for N=8.
first-min.jpg
0

LVL 84

Expert Comment

ID: 39949655
And does TommySzalapski's hint suggest a way to modify that yo find the second and third minimum?
0

LVL 10

Author Comment

ID: 39949659
No, he only pointed out that if you can do it for the first it's no problem to do the second and third. But that wasn't what I asked. I asked to do it for the minimum in the first place.

Anyway, thank you all for your time, points will be split.
0

LVL 10

Author Closing Comment

ID: 39949660
Thanks again.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This is a research brief on the potential colonization of humans on Mars.
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computersâ€¦
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templaâ€¦
###### Suggested Courses
Course of the Month11 days, 14 hours left to enroll