A General Definition of the O-notation for Algorithm Analysis

Kalle Matias Rutanen; German Gomez Herrero; Sirkka-Liisa Anneli Eriksson; Karen Egiazarian

A General Definition of the O-notation for Algorithm Analysis

Kalle Matias Rutanen
, German Gomez Herrero
, Sirkka-Liisa Anneli Eriksson
, Karen Egiazarian

Tutkimustuotos: Artikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

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.

Alkuperäiskieli	Englanti
Sivumäärä	33
Julkaisu	Bulletin of the European Association for Theoretical Computer Science
Numero	117
Tila	Julkaistu - 21 lokak. 2015
OKM-julkaisutyyppi	A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

Julkaisufoorumi-taso

Ei tasoa

Pääsy asiakirjaan

http://bulletin.eatcs.org/index.php/beatcs/article/view/373/354

Muut tiedostot ja linkit

Link to whole issue

Siteeraa tätä

@article{3f91f9c955a54607ba7c15f370865441,

title = "A General Definition of the O-notation for Algorithm Analysis",

abstract = "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.",

keywords = "O-notation, algorithm analysis, Complexity analysis",

author = "Rutanen, \{Kalle Matias\} and \{Gomez Herrero\}, German and Eriksson, \{Sirkka-Liisa Anneli\} and Karen Egiazarian",

note = "ORG=mat,0.5 ORG=sgn,0.5 EXT={"}Gomez Herrero, German{"}",

year = "2015",

month = oct,

day = "21",

language = "English",

journal = "Bulletin of the European Association for Theoretical Computer Science",

issn = "0252-9742",

number = "117",

}

TY - JOUR

T1 - A General Definition of the O-notation for Algorithm Analysis

AU - Rutanen, Kalle Matias

AU - Gomez Herrero, German

AU - Eriksson, Sirkka-Liisa Anneli

AU - Egiazarian, Karen

N1 - ORG=mat,0.5 ORG=sgn,0.5 EXT="Gomez Herrero, German"

PY - 2015/10/21

Y1 - 2015/10/21

N2 - 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.

AB - 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.

KW - O-notation

KW - algorithm analysis

KW - Complexity analysis

UR - https://www.eatcs.org/images/bulletin/beatcs117.pdf

M3 - Article

SN - 0252-9742

JO - Bulletin of the European Association for Theoretical Computer Science

JF - Bulletin of the European Association for Theoretical Computer Science

IS - 117

ER -

A General Definition of the O-notation for Algorithm Analysis

Abstrakti

Julkaisufoorumi-taso

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Siteeraa tätä