Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 0 down vote favorite

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.

share|improve this question
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

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.