What does O(n) mean?

  • Yuri Gurevich

SIGACT NEWS 17 |

In “Crusade for Better Notation” [1], Gilles Brassard calls one-way equations involving big omicron, big omega, etc. “bad, irrational and confusing notation”. He promotes the following alternative that seems to him better and more natural: define O(t(n)), Ω (t(n)), etc. as sets and “use them as such, in accordance with set theory”. However, the new notation calls for extending arithmetic operations (and, in due course, some other operations) from functions to sets of functions, and gives rise, as Gilles Brassard honestly and immediately acknowledges, to a new type of ambiguous expressions like [O(n)]2 or 2O(n). This does not seem very convenient to me, and I will try to defend the traditional notation here.