A New Look at Worst Case Complexity: A Statistical Approach

Niraj Kumar Singh, Soubhik Chakraborty and Dheeresh Kumar Mallick

International Journal of Analysis, 2014, vol. 2014, 1-10

Abstract:

We present a new and improved worst case complexity model for quick sort as , where the LHS gives the worst case time complexity, is the input size, is the frequency of sample elements, and is a function of both the input size and the parameter . 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, , which stems from the worst case complexity for this algorithm.

Date: 2014
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/ANALYSIS/2014/840432.pdf (application/pdf)
http://downloads.hindawi.com/journals/ANALYSIS/2014/840432.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:ijanal:840432

DOI: 10.1155/2014/840432

Access Statistics for this article

More articles in International Journal of Analysis from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().