Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Puzzle: The Ham Cheese Sandwich cut.

by Perl Mouse (Chaplain)
on Nov 18, 2005 at 10:12 UTC ( [id://509722]=note: print w/replies, xml ) Need Help??


in reply to Re: Puzzle: The Ham Cheese Sandwich cut.
in thread Puzzle: The Ham Cheese Sandwich cut.

One of these is randomized and runs in expected O(n) time.

The rest of this post shows my implementation.

Nice, but the worst case running time is Ω(n2). It suffers from the same problem as Quicksort: picking a random pivot works well often enough to get a good expected running time, but if you're unlucky, it's really slow.

There is an algorithm to do it in garanteed linear time (although when done in Perl, the constants are so high that for most practical situations, one can better use sorting in C and picking the middle element).

Perl --((8:>*
  • Comment on Re^2: Puzzle: The Ham Cheese Sandwich cut.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://509722]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2024-03-29 15:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found