TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

Minimal Characterization of O-notation in Algorithm Analysis

Tutkimustuotos: vertaisarvioituArtikkeli

Yksityiskohdat

AlkuperäiskieliEnglanti
JulkaisuTheoretical Computer Science
DOI - pysyväislinkit
TilaE-pub ahead of print - 27 joulukuuta 2017
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

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.

Tutkimusalat

Julkaisufoorumi-taso