A better algorithm

[razzle]

an avarage "with respect to everything" is either non-sense or it can be reduced to the choice of a ( possibly degenerate and/or a family of ) probability space.

It was just a way of describing "any possible input" because that's how I define "average input".

My point was that using the OP's input (even in the form of a probability distribution) as you suggested won't give the average-case complexity of the algorithm. For that all possible inputs should be considered, not just one specific. It's a conceptual insight independent of any mathematical formalism such as probability theory.

I stop here because I know you're a probabilities fanatic who cannot fathom anything that doesn't come with a distribution. A discussion would go on forever or break down completely when you introduce that compass again.