# How to explain rigorously that quick sort is faster than say buble sort?

I can appreciate that in most instances, quick sort would avoid from repeated operations, in compare to an exhaustive method. But, how one can demonstrate this fact in a rigorous fashion, and preferably generalizable way. For example, by algebraic methods and structural comparison of algorithms.

-
They're the same in the worst case, so you must be talking average case. Start by defining the space over which you're averaging... –  Peter Taylor Sep 14 '12 at 12:27
As @Peter mentioned, a rigorous proof that quicksort is faster than bubblesort depends strongy on what you mean by "faster". Depending on how the two algorithms are defined, there might be inputs for which bubblesort is faster than quicksort and vice versa. It is true, though, that quicksort runs faster on average than bubblesort. Average-case analysis is generally ugly to do, look here for example, and scroll down to "average case analysis" to see what I mean by "ugly". –  Rick Decker Sep 14 '12 at 13:02