A New Look at Worst Case Complexity: A Statistical Approach

摘要

We present a new and improved worst case complexity model for quick sort asyworst(n,td)=b0+b1n2+g(n,td)+ɛ, where the LHS gives the worst case time complexity,nis the input size,tdis the frequency of sample elements, andg(n,td)is a function of both the input sizenand the parametertd. The rest of the terms arising due to linear regression have usual meanings. We claim this to be an improvement over the conventional model; namely,yworst(n)=b0+b1n+b2n2+ɛ, which stems from the worst caseO(n2)complexity for this algorithm.