Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

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

by hv (Prior)
on Nov 22, 2005 at 13:19 UTC ( [id://510764]=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.

I suspect that a proof of the running time order will concentrate on the expected depth of recursion.

However I believe it will be much harder to prove that the push is O(1) - indeed I suspect it is not - and without that the algorithm as a whole cannot be O(n).

Hugo

Replies are listed 'Best First'.
Re^3: Puzzle: The Ham Cheese Sandwich cut.
by Perl Mouse (Chaplain) on Nov 22, 2005 at 14:05 UTC
    No, the proof doesn't need an expected running time. The running time T(N) is expressed as:
    T(N) = T(N/5) + T(7N/10 + 10) + Ο(N);
    which has T(N) = Ο(N) as a solution.
    However I believe it will be much harder to prove that the push is O(1) - indeed I suspect it is not - and without that the algorithm as a whole cannot be O(n).
    It doesn't have to be. What's needed is that the push has an amortized running time of Ο(1) - that is, if we perform N pushes, the total running time is still bounded by Ο(N). And from what I understand of how allocation of array sizes work (an addition extra 20% memory is being claimed), a push has an amortized Ο(1) performance. A single push may take Θ(N) running time, but N pushes average it out.
    Perl --((8:>*
[reply]

In Section Meditations

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://510764]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2024-04-18 02:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found