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

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

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.

Original language	English
Pages (from-to)	31-41
Journal	Theoretical Computer Science
Volume	713
Early online date	27 Dec 2017
DOIs	https://doi.org/10.1016/j.tcs.2017.12.026
Publication status	Published - Feb 2018
Publication type	A1 Journal article-refereed

Keywords

O-notation
characterization
minimal

Publication forum classification

Publication forum level 2

Access to Document

10.1016/j.tcs.2017.12.026

Cite this

@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 B.V.",

}

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

Abstract

Keywords

Publication forum classification

Access to Document

Fingerprint

Cite this