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