Why do we use the term "asymptotic" in complexity. Although I know what an asymptote is, but what is an asymptote doing here?


There are several answers to this.

  1. "Asymptotic" here means "as something tends to infinity". It has indeed nothing to do with curves.

  2. There is no such thing as "complexity notation". We denote "complexities" using asymptotic notation, more specifically Landau notataion.

  3. "Complexity" is a mostly empty, overused and overloaded term.

    However, in the context of algorithms in TCS, it is usally agreed upon that it means "the $\Theta$-class (also "order of growth") of the worst-case running-time cost function" of a given algorithm.

    Similarly the "complexity" of a problem means "the best worst-case complexity among all algorithms for this problem".

    These can be overridden by adding qualifiers, e.g. "average-case space complexity".

Note that item 3 is my own opinion; some people disagree. You will indeed find "complexity" used for many things in the literature and on this site. In case of doubt or ambiguity, ask the author.

| cite | improve this answer | |
  • $\begingroup$ okay it means the problem of which we find complexity are actually asymptotes..which tends to infinity??am i right?? $\endgroup$ – aditya lath Mar 3 '16 at 8:30
  • 1
    $\begingroup$ @adityalath I don't even understand what you are saying. In all my years in CS, I've never seen the term "asymptote" used. You may want to peruse our introductory reference questions, in particular this one. $\endgroup$ – Raphael Mar 3 '16 at 13:50

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".

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.