Tampere University of Technology

TUTCRIS Research Portal

A General Definition of the O-notation for Algorithm Analysis

Research output: Contribution to journalArticleScientificpeer-review

Details

Original languageEnglish
Number of pages33
JournalBulletin of EATCS
Issue number117
Publication statusPublished - 21 Oct 2015
Publication typeA1 Journal article-refereed

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

Publication forum classification

Field of science, Statistics Finland