TUTCRIS - Tampereen teknillinen yliopisto

TUTCRIS

A General Definition of the O-notation for Algorithm Analysis

Tutkimustuotosvertaisarvioitu

Yksityiskohdat

AlkuperäiskieliEnglanti
Sivumäärä33
JulkaisuBulletin of EATCS
Numero117
TilaJulkaistu - 21 lokakuuta 2015
OKM-julkaisutyyppiA1 Alkuperäisartikkeli

Tiivistelmä

We provide an extensive list of desirable properties for an O-notation —
as used in algorithm analysis — and reduce them to 8 primitive properties.
We prove that the primitive properties are equivalent to the definition of the
O-notation as linear dominance.

Tutkimusalat

Julkaisufoorumi-taso