Minimal Characterization of O-notation in Algorithm Analysis

Kalle Rutanen

doi:10.1016/j.tcs.2017.12.026

Minimal Characterization of O-notation in Algorithm Analysis

Kalle Rutanen

Tutkimustuotos: Artikkeli › Scientific › vertaisarvioitu

Abstrakti

Previously, we showed that linear dominance is the only definition of O-notation suitable for algorithm analysis [1,2]. Linear dominance was characterized by 8 primitive properties as a down-set of a non-trivial scale-invariant preorder which is preserved under certain modifications to algorithms and is consistent with pointwise partial order. In this paper, we provide a minimal characterization of O-notation, where there are no redundant properties. Such is given by excluding locality from primitive properties.

Alkuperäiskieli	Englanti
Sivut	31-41
Julkaisu	Theoretical Computer Science
Vuosikerta	713
Varhainen verkossa julkaisun päivämäärä	27 jouluk. 2017
DOI - pysyväislinkit	https://doi.org/10.1016/j.tcs.2017.12.026
Tila	Julkaistu - helmik. 2018
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Julkaisufoorumi-taso

Jufo-taso 2

Pääsy asiakirjaan

10.1016/j.tcs.2017.12.026

Siteeraa tätä

@article{459e725c3de243cfa0960424f69e64bb,

title = "Minimal Characterization of O-notation in Algorithm Analysis",

abstract = "Previously, we showed that linear dominance is the only definition of O-notation suitable for algorithm analysis [1,2]. Linear dominance was characterized by 8 primitive properties as a down-set of a non-trivial scale-invariant preorder which is preserved under certain modifications to algorithms and is consistent with pointwise partial order. In this paper, we provide a minimal characterization of O-notation, where there are no redundant properties. Such is given by excluding locality from primitive properties.",

keywords = "O-notation, characterization, minimal",

author = "Kalle Rutanen",

year = "2018",

month = feb,

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

language = "English",

volume = "713",

pages = "31--41",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Minimal Characterization of O-notation in Algorithm Analysis

AU - Rutanen, Kalle

PY - 2018/2

Y1 - 2018/2

N2 - Previously, we showed that linear dominance is the only definition of O-notation suitable for algorithm analysis [1,2]. Linear dominance was characterized by 8 primitive properties as a down-set of a non-trivial scale-invariant preorder which is preserved under certain modifications to algorithms and is consistent with pointwise partial order. In this paper, we provide a minimal characterization of O-notation, where there are no redundant properties. Such is given by excluding locality from primitive properties.

AB - Previously, we showed that linear dominance is the only definition of O-notation suitable for algorithm analysis [1,2]. Linear dominance was characterized by 8 primitive properties as a down-set of a non-trivial scale-invariant preorder which is preserved under certain modifications to algorithms and is consistent with pointwise partial order. In this paper, we provide a minimal characterization of O-notation, where there are no redundant properties. Such is given by excluding locality from primitive properties.

KW - O-notation

KW - characterization

KW - minimal

U2 - 10.1016/j.tcs.2017.12.026

DO - 10.1016/j.tcs.2017.12.026

M3 - Article

SN - 0304-3975

VL - 713

SP - 31

EP - 41

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Minimal Characterization of O-notation in Algorithm Analysis

Abstrakti

Julkaisufoorumi-taso

Pääsy asiakirjaan

Sormenjälki

Siteeraa tätä