4
$\begingroup$

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

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ okay it means the problem of which we find complexity are actually asymptotes..which tends to infinity??am i right?? $\endgroup$ Commented Mar 3, 2016 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
    Commented Mar 3, 2016 at 13:50
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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