patternMinor
Why are Complexity Notations Called Asymptotic?
Viewed 0 times
whycalledareasymptoticcomplexitynotations
Problem
Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?
Solution
I would like to quote from "Concrete Mathematics" (Chapter 9) by Ronald Graham, Donald Knuth, and Oren Patashnik. It does mention curves and asymptotes.
The word asymptotic stems from a Greek root meaning "not falling together". When ancient Greek mathematicians studied conic sections, they considered hyperbolas like the graph of $y = \sqrt{1 + x^2}$ which has the lines $y = x$ and $y = -x$ as "asymptotes". The curve approaches but never quite touches these asymptotes, when $x \to \infty$.
Nowadays we use "asymptotic" in a broader sense to mean any approximate value that gets closer and closer to the truth, when some parameter approaches a limiting value [emphasis added]. For us, asymptotics means "almost falling together".
The word asymptotic stems from a Greek root meaning "not falling together". When ancient Greek mathematicians studied conic sections, they considered hyperbolas like the graph of $y = \sqrt{1 + x^2}$ which has the lines $y = x$ and $y = -x$ as "asymptotes". The curve approaches but never quite touches these asymptotes, when $x \to \infty$.
Nowadays we use "asymptotic" in a broader sense to mean any approximate value that gets closer and closer to the truth, when some parameter approaches a limiting value [emphasis added]. For us, asymptotics means "almost falling together".
Context
StackExchange Computer Science Q#53931, answer score: 7
Revisions (0)
No revisions yet.