Simplified complexity analysis of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT

Rezaul Alam Chowdhury; M. Kaykobad; Suman Kumar Nath

doi:10.1080/00207160008804896

Simplified complexity analysis of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT

Rezaul Alam Chowdhury
, M. Kaykobad
, Suman Kumar Nath

Computer Science

Stony Brook University

Bangladesh University of Engineering and Technology

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

1 Scopus citations

Abstract

McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which requires nlog₂n+n element comparisons (for n = 2^h+1 - 1) in the worst case, but requires an extra storage of n bits. Ingo Wegener (1992) has analyzed the average and worst case complexity of the algorithm which is very complex and long. In this paper we present a simplified complexity analysis of the same algorithm from a different viewpoint. For n = 2^h+1 - 1, we show that it requires nlog₂n+n element comparisons in the worst case and nlog₂n+0.42n comparisons on the average.

Original language	English
Pages (from-to)	293-297
Number of pages	5
Journal	International Journal of Computer Mathematics
Volume	73
Issue number	3
DOIs	https://doi.org/10.1080/00207160008804896
State	Published - 2000

Access to Document

10.1080/00207160008804896

Cite this

@article{67a2b61a364f4465916becacb7f5bac1,

title = "Simplified complexity analysis of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT",

abstract = "McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which requires nlog2n+n element comparisons (for n = 2h+1 - 1) in the worst case, but requires an extra storage of n bits. Ingo Wegener (1992) has analyzed the average and worst case complexity of the algorithm which is very complex and long. In this paper we present a simplified complexity analysis of the same algorithm from a different viewpoint. For n = 2h+1 - 1, we show that it requires nlog2n+n element comparisons in the worst case and nlog2n+0.42n comparisons on the average.",

author = "Chowdhury, \{Rezaul Alam\} and M. Kaykobad and Nath, \{Suman Kumar\}",

year = "2000",

doi = "10.1080/00207160008804896",

language = "English",

volume = "73",

pages = "293--297",

journal = "International Journal of Computer Mathematics",

issn = "0020-7160",

publisher = "Taylor and Francis Ltd.",

number = "3",

}

TY - JOUR

T1 - Simplified complexity analysis of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT

AU - Chowdhury, Rezaul Alam

AU - Kaykobad, M.

AU - Nath, Suman Kumar

PY - 2000

Y1 - 2000

N2 - McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which requires nlog2n+n element comparisons (for n = 2h+1 - 1) in the worst case, but requires an extra storage of n bits. Ingo Wegener (1992) has analyzed the average and worst case complexity of the algorithm which is very complex and long. In this paper we present a simplified complexity analysis of the same algorithm from a different viewpoint. For n = 2h+1 - 1, we show that it requires nlog2n+n element comparisons in the worst case and nlog2n+0.42n comparisons on the average.

AB - McDiarmid and Reed (1989) presented a variant of BOTTOM-UP-HEAPSORT which requires nlog2n+n element comparisons (for n = 2h+1 - 1) in the worst case, but requires an extra storage of n bits. Ingo Wegener (1992) has analyzed the average and worst case complexity of the algorithm which is very complex and long. In this paper we present a simplified complexity analysis of the same algorithm from a different viewpoint. For n = 2h+1 - 1, we show that it requires nlog2n+n element comparisons in the worst case and nlog2n+0.42n comparisons on the average.

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

U2 - 10.1080/00207160008804896

DO - 10.1080/00207160008804896

M3 - Article

SN - 0020-7160

VL - 73

SP - 293

EP - 297

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 3

ER -

Simplified complexity analysis of McDiarmid and Reed's variant of BOTTOM-UP-HEAPSORT

Abstract

Access to Document

Other files and links

Fingerprint

Cite this