Indexing functions and time lower bounds for sorting on a mesh-connected computer

Yijie Han; Yoshihide Igarashi; Miroslaw Truszczynski

doi:10.1016/0166-218X(92)90228-3

Indexing functions and time lower bounds for sorting on a mesh-connected computer

Yijie Han, Yoshihide Igarashi, Miroslaw Truszczynski

Computer Science

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

5 Scopus citations

Abstract

We introduce a parameter of indexing functions and show its relation to lower bounds for sorting algorithms on mesh-connected computers that follow from the Chain Theorem. We give lower and upper bounds for the parameter. Conclusions from our results are: (1) no matter what indexing function is used any sorting algorithm must execute 2.27n + Θ(1) steps; (2) the best lower bound true for all indexing functions that we can hope to prove by the Chain Theorem argument is 2.5n + Θ(1).

Original language	English
Pages (from-to)	141-152
Number of pages	12
Journal	Discrete Applied Mathematics
Volume	36
Issue number	2
DOIs	https://doi.org/10.1016/0166-218X(92)90228-3
State	Published - Apr 30 1992

Bibliographical note

Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

Keywords

Sorting
complexity
indexing function
indexing scheme
lower bound
mesh-connected processor array
parallel computation

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/0166-218X(92)90228-3

Cite this

@article{6c7a069d97824600ba2fb86fbbc1668e,

title = "Indexing functions and time lower bounds for sorting on a mesh-connected computer",

abstract = "We introduce a parameter of indexing functions and show its relation to lower bounds for sorting algorithms on mesh-connected computers that follow from the Chain Theorem. We give lower and upper bounds for the parameter. Conclusions from our results are: (1) no matter what indexing function is used any sorting algorithm must execute 2.27n + Θ(1) steps; (2) the best lower bound true for all indexing functions that we can hope to prove by the Chain Theorem argument is 2.5n + Θ(1).",

keywords = "Sorting, complexity, indexing function, indexing scheme, lower bound, mesh-connected processor array, parallel computation",

author = "Yijie Han and Yoshihide Igarashi and Miroslaw Truszczynski",

year = "1992",

month = apr,

day = "30",

doi = "10.1016/0166-218X(92)90228-3",

language = "English",

volume = "36",

pages = "141--152",

number = "2",

}

TY - JOUR

T1 - Indexing functions and time lower bounds for sorting on a mesh-connected computer

AU - Han, Yijie

AU - Igarashi, Yoshihide

AU - Truszczynski, Miroslaw

PY - 1992/4/30

Y1 - 1992/4/30

N2 - We introduce a parameter of indexing functions and show its relation to lower bounds for sorting algorithms on mesh-connected computers that follow from the Chain Theorem. We give lower and upper bounds for the parameter. Conclusions from our results are: (1) no matter what indexing function is used any sorting algorithm must execute 2.27n + Θ(1) steps; (2) the best lower bound true for all indexing functions that we can hope to prove by the Chain Theorem argument is 2.5n + Θ(1).

AB - We introduce a parameter of indexing functions and show its relation to lower bounds for sorting algorithms on mesh-connected computers that follow from the Chain Theorem. We give lower and upper bounds for the parameter. Conclusions from our results are: (1) no matter what indexing function is used any sorting algorithm must execute 2.27n + Θ(1) steps; (2) the best lower bound true for all indexing functions that we can hope to prove by the Chain Theorem argument is 2.5n + Θ(1).

KW - Sorting

KW - complexity

KW - indexing function

KW - indexing scheme

KW - lower bound

KW - mesh-connected processor array

KW - parallel computation

UR - http://www.scopus.com/inward/record.url?scp=38249011756&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249011756&partnerID=8YFLogxK

U2 - 10.1016/0166-218X(92)90228-3

DO - 10.1016/0166-218X(92)90228-3

M3 - Article

AN - SCOPUS:38249011756

SN - 0166-218X

VL - 36

SP - 141

EP - 152

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 2

ER -

Indexing functions and time lower bounds for sorting on a mesh-connected computer

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this