Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6875621 | Theoretical Computer Science | 2018 | 15 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Kalle Rutanen,