Asymptote used to refer to a line in math that is tangent to a curve at infinity.

Asymptotic notation in computational complexity refers to limiting behavior of a function whose domain and range is Z+, it is valid for values of domain that are greater than a particular threshold. Thus, here we approximate curves with curves. Often, preferably the we seek curve(s) that track the original curve closely.

Different notations come into picture corr. to the type of bound i.e. upper, lower or both (tracking from above, below or both (with a hidden multiplicative constant)). Further some bounds are tight (to denote the complexity of a given algorithm) and others are loose (intentionally in case of comparing different algorithms for the same problem). Occasionally, we live with a loose bound when indeed we seek a tight one because it is much easier to estimate the recurrence instead of solving it exactly.

Best regards.

Thanks, One more Question! :) I have seen in some literature that the Best Case , Worst Case and Average Case are represented by Theta(n). for example I have seen the following for Binary Search:

Successful Search:

Best Case : Theta(1)

Average Case: Theta(lg n)

Worst Case: Theta(lg n)

My question is Why we represent Worst Case by Theta (or Tight Bounds) when we have Big Oh (Upper Bound) for that.

This confusion is shared by many students. Let an algorithm say binary search be called A.

We can simply say that A has O( log_2 n) time complexity. However, when we speak about the Best , the Average and the Worst Cases we are not referring to A per se. Theta is used to indicate that we can have a tight bound for each of these cases (as opposed to A). I hope it clarifies. Regards.

Regarding the theta notation, It says that if f(n) = theta(g(n)), f(n) will act exactly like g(n). Lets take binary search example. We can say that worst case complexity of binary search is O(n) or even O(2^n). These statements are correct because running time of binary search does not grow faster than c*n or c*2^n for a positive constant c. However it doesn't give us much precision, does it? But saying that worst case running time is theta(log n) is gives us the idea of the algorithm's behaviour immediately.

Big Oh is useful when obtaining a theta bound is much harder than obtaining an upper bound. Generally it is sufficient to show that it is not worse than some other function. But sometimes you need much more precise understanding about algorithms behaviour. That is where theta is needed.

Thanks to all.

Could somebody give some example to better clarify the concept of 'asymptotic' or 'asymptotically close to...' etc.

I have found these definitions somewhere on web :

'Generally, asymptotic means approaching but never connecting with a line or curve. '

'The term asymptotic means approaching a value or curve arbitrarily closely (i.e., as some sort of limit is taken). A line or curve that is asymptoticto given curve is called the asymptote of .'

Dear Muhammad Yasir,

Asymptotic or asymptotically close to are treated synonymous in time complexity terminology of computer science.

Consider f(n)= n^3+ 4 n^2 + n and g(n)=n^3 - 4 n^2 + n defined for all n>3. Clearly the functions are not identical. However, for large integer values of n, the term that dominates both functions is n^3. Further limit_{ n \rightarrow \infty } f(n)/ g(n) and limit_{ n \rightarrow \infty } g(n)/ f(n) both equal 1. Thus, the functions are asymptotically equivalent. Further, even if limit_{ n \rightarrow \infty } f(n)/ g(n)= \alpha for some positive real \alpha then also they are treated as equivalent. Note that in this case limit_{ n \rightarrow \infty } g(n)/ f(n)= 1/(\alpha) and because RHS here also is a constant this condition suffices. That is, f(n)= n^3+ 4 n^2 + n , 2g(n), g(n)/2, k*g(n) and k*f(n) (for some positive k) are equivalent.

I hope that this helps.

Regards.