A New Look at Worst Case Complexity: A Statistical Approach. (28th December 2014)

• Record Type: Journal Article
• Authors: Singh, Niraj Kumar; Chakraborty, Soubhik; Mallick, Dheeresh Kumar
• Other Names: Cahlon Baruch Academic Editor.
• Is Part Of: International journal of analysis. Volume 2014(2014)
• Publication Date: 2014-12-28
• Subjects: Mathematical analysis -- Periodicals; 515.05
• DOI: 10.1155/2014/840432
• Languages: English
• ISSNs: 2314-498X

Abstract

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.