patternMinor
Is Green's the best 16-input sorting network so far?
Viewed 0 times
sortingtheinputfargreennetworkbest
Problem
Every paper says that Green's construction is the best 16-input sorting
network as for now.
But why does Wikipedia says: "Size, lower bound: 53"?
I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?
network as for now.
But why does Wikipedia says: "Size, lower bound: 53"?
I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?
Solution
No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.
Context
StackExchange Computer Science Q#60242, answer score: 8
Revisions (0)
No revisions yet.