A New Look at Worst Case Complexity: A Statistical Approach. (28th December 2014) - Singh, Niraj Kumar; Chakraborty, Soubhik; Mallick, Dheeresh Kumar
Abstract : We present a new and improved worst case complexity model for quick sort asy worst ( n, t d ) = b 0 + b 1 n 2 + g ( n, t d ) + ɛ, where the LHS gives the worst case time complexity, n is the input size, t d is the frequency of sample elements, andg ( n, t d ) is a function of both the input sizen and the parametert d . 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, y worst ( n ) = b 0 + b 1 n + b 2 n 2 + ɛ, which stems from the worst caseO ( n 2 ) complexity for this algorithm.