A General Definition of the O-notation for Algorithm Analysis

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

    Research output: Contribution to journalArticleScientificpeer-review

    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.
    Original languageEnglish
    Number of pages33
    JournalBulletin of EATCS
    Issue number117
    Publication statusPublished - 21 Oct 2015
    Publication typeA1 Journal article-refereed

    Keywords

    • O-notation
    • algorithm analysis
    • Complexity analysis

    Publication forum classification

    • No publication forum level

    Cite this