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.
