Landing : Athabascau University

COMP372 Abuses of asymptotic notation

  • Public
By Craig Belair in the group COMP372 Design and Analysis of Algorithms January 12, 2020 - 11:22pm
 

One of the most common abuses of asymptotic notation is the use of the "=" sign when representing set membership. For example, we might write f(x)=12x3+5x2+x+3 = Θ(x3). Clearly it would be more proper to write f(x)∈Θ(x3). Often times, however, our asymptotic classes behave similarly to algebraic expressions. For example, if f(x)∈Θ(x3) and g(x)∈Θ(x5), we can therefore conclude that [f(x)+g(x)]∈[Θ(x3+x5)]. The use of the equals sign helps us to associate our algebraic intuition with the concepts of asymptotic analysis.

Another common abuse is to refer to steps that run in constant time as Θ(1) operations. While it is true that any constant time operation can be bound above and below by some constants c1, c2 > 0, the use of Θ(1) rather than Θ(x0) makes it unclear as to what variable our run time depends on. Of course, the Θ(1) notation is avoided when there may be any important ambiguity.

COMP372 Design and Analysis of Algorithms

COMP372 Design and Analysis of Algorithms

This is for course discussion.