Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I am reading the following in a book on algorithms (Cormen's to be specific):

That is, we are concerned with how the running time of an algorithm increases with the size of the input in the limit, as the size of the input increases without bound.

I can not understand what is the meaning of the phrase: with the size of the input in the limit.
What is the limit refering about?

UPDATE:

Please note that at this point in the book (early fundamentals of chapter 2) there has been no formal definition or mention of Big O or other asymptotic notation except a vague reference on Theta notation

Any help?

share|improve this question
    
That isn't really a formal statement; a formal statement would be essentially big-O notation, with or without the usual notation. –  David Thornley Oct 24 '11 at 16:30
    
Yes.I was meaning that the way it is phrased is very formal –  user10326 Oct 24 '11 at 19:23
    
The author got his PhD in CS around the same time you were born. Please forgive him for not being very good at imagining what it is like to not know any math or computer science. I bet he learned calculus before high school. Calculus is all you need here. –  Job Oct 25 '11 at 3:38
    
I forgive him :-) –  user10326 Oct 25 '11 at 4:21
    
See this link for the explanation of the Infinite Limit en.wikibooks.org/wiki/Calculus/Infinite_Limits –  Carlo Kuip Oct 28 '11 at 10:31
add comment

2 Answers 2

Look at the formal definition of Big O notation to see a limit defined within the notation there. While Big O is specifically about worst case complexity there are other notations for average case or best case.

Usually the idea is to get an upper bound of how bad does the algorithm run. Is the complexity logarithmic, linear, quadratic, or exponential? There are various examples one can give for some of those as a binary search can have logarithmic complexity as one is reducing half the options with each search assuming the initial set of data is sorted. Quadratic would be various poor sorting algorithms like Bubble Sort.


An alternative view here is to note that "the size of the input increases without bound" is generally a way of describing a limit as a variable tends to infinity. Limits to Infinity would be an example discussing f(x) = 1/x where as x grows without bound, the function value will approach zero. The key is to imagine the running time of the algorithm as a function depending on the size of the input and as one changes that input, how quickly is the function growing. Is it a straight line or a curve? How steep is the slope at any point? That is kind of the point behind the idea here.

share|improve this answer
1  
JB King:OK I will read this, but in this paragraph, the writers have not yet introduced the Big O notation.So since it has not been yet introduced, it confuses me that they use this concept here which is in the chapter Fundamentals –  user10326 Oct 24 '11 at 16:07
add comment

It means that as the size of the input increases infinitely, what is the running time in relation to the input. Big O can be used to measure any factor, including memory, but is usually time.

share|improve this answer
1  
Please see update of OP. No Big O mentioned so far in book –  user10326 Oct 24 '11 at 16:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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