Minimal Characterization of O-notation in Algorithm Analysis
Research output: Contribution to journal › Article › Scientific › peer-review
|Journal||Theoretical Computer Science|
|Early online date||27 Dec 2017|
|Publication status||Published - Feb 2018|
|Publication type||A1 Journal article-refereed|
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.
- O-notation, characterization, minimal