Minimal Characterization of O-notation in Algorithm Analysis

Kalle Rutanen

    Research output: Contribution to journalArticleScientificpeer-review


    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 languageEnglish
    Pages (from-to)31-41
    JournalTheoretical Computer Science
    Early online date27 Dec 2017
    Publication statusPublished - Feb 2018
    Publication typeA1 Journal article-refereed


    • O-notation
    • characterization
    • minimal

    Publication forum classification

    • Publication forum level 2


    Dive into the research topics of 'Minimal Characterization of O-notation in Algorithm Analysis'. Together they form a unique fingerprint.

    Cite this