Running time of the Treapsort algorithm

D. Early; M. Schellekens

doi:10.1016/j.tcs.2013.03.012

Running time of the Treapsort algorithm

D. Early
, M. Schellekens

School of Computer Science and Information Technology

University College Cork

Research output: Contribution to journal › Article › peer-review

Abstract

We analyse the running time of Treapsort, a sorting algorithm in the MOQA¹ programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Θ(σ^-1nlnn) for treaps of size n. We also show that the multiset of running times of Treapsort on all treaps of size n is equal to the multiset of running times of Quicksort on all lists of length n.

Original language	English
Pages (from-to)	65-73
Number of pages	9
Journal	Theoretical Computer Science
Volume	487
DOIs	https://doi.org/10.1016/j.tcs.2013.03.012
Publication status	Published - 27 May 2013

Keywords

Average-case analysis of algorithms
MOQA
Smoothed complexity
Sorting algorithms

Access to Document

10.1016/j.tcs.2013.03.012

Cite this

@article{2391e93533374cdba9f2c26fcb7f8319,

title = "Running time of the Treapsort algorithm",

abstract = "We analyse the running time of Treapsort, a sorting algorithm in the MOQA1 programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Θ(σ-1nlnn) for treaps of size n. We also show that the multiset of running times of Treapsort on all treaps of size n is equal to the multiset of running times of Quicksort on all lists of length n.",

keywords = "Average-case analysis of algorithms, MOQA, Smoothed complexity, Sorting algorithms",

author = "D. Early and M. Schellekens",

year = "2013",

month = may,

day = "27",

doi = "10.1016/j.tcs.2013.03.012",

language = "English",

volume = "487",

pages = "65--73",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Running time of the Treapsort algorithm

AU - Early, D.

AU - Schellekens, M.

PY - 2013/5/27

Y1 - 2013/5/27

N2 - We analyse the running time of Treapsort, a sorting algorithm in the MOQA1 programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Θ(σ-1nlnn) for treaps of size n. We also show that the multiset of running times of Treapsort on all treaps of size n is equal to the multiset of running times of Quicksort on all lists of length n.

AB - We analyse the running time of Treapsort, a sorting algorithm in the MOQA1 programming language, which acts on treaps. We show that, using the 'partial permutation' model of Banderier et al. (2003) [1], Treapsort has smoothed complexity Θ(σ-1nlnn) for treaps of size n. We also show that the multiset of running times of Treapsort on all treaps of size n is equal to the multiset of running times of Quicksort on all lists of length n.

KW - Average-case analysis of algorithms

KW - MOQA

KW - Smoothed complexity

KW - Sorting algorithms

UR - https://www.scopus.com/pages/publications/84877584646

U2 - 10.1016/j.tcs.2013.03.012

DO - 10.1016/j.tcs.2013.03.012

M3 - Article

AN - SCOPUS:84877584646

SN - 0304-3975

VL - 487

SP - 65

EP - 73

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Running time of the Treapsort algorithm

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this