Hi guys, to sum up I've learnt a good material about Data structure and Algorithms, but there's something really internally harassing me and still confused .... I hope by you guys this perplexed idea be solved.

Why we are looking to the time of algorithm's behavior over "infinity" and not over something constant? what does it stand for? I mean for example we do compare two algorithms of time complexity by aiming the inputs to infinity .... and then comparing between its time complexity ? ..why I need for determining the time complexity of algorithm I must see its behavior over infinity and then I can determine it?

that's point "why comparing time complexity over specifically infinity" is still confusing me and a lil "fuzzy" .. if there's any analogs to clear that point out..would be much appreciated! thank you guys alot.
really, I know what is O and omega nad theta but still something internally hidden for me which why exactly we determine time of complexity by its behavior in infinity !

** by the way I know by the definition O/omega/tetha implicitly saying that we must determine time of complexity of algorithm over infinity ..my question why over infinity .. **

 

Don't think of it telling you something about the algorithm "at infinity", but rather something about how the algorithm behaves for "sufficiently large" problems. How large is sufficiently large? That depends on the problem and the implementation of the algorithm. For some, anything over a data set consisting of 10 things might be large enough, while for others it might need to be 100,000 and for others even larger. In general, we don't know how big is big enough, so we look at the behavior as the problem size grows arbitrarily large (i.e., as the problem size goes towards infinity).

 

Don't think of it telling you something about the algorithm "at infinity", but rather something about how the algorithm behaves for "sufficiently large" problems. How large is sufficiently large? That depends on the problem and the implementation of the algorithm. For some, anything over a data set consisting of 10 things might be large enough, while for others it might need to be 100,000 and for others even larger. In general, we don't know how big is big enough, so we look at the behavior as the problem size grows arbitrarily large (i.e., as the problem size goes towards infinity).

my idea is "why actually we are looking to it as sufficiently large?" I don't have problem with the symbol infinity, but I meant that I have problem with the concept why we are looking to the problem how it behaves in sufficient large amount?!! "I'm not succeeding to understand the concept of why we need to look on time complexity of algorithm of how behaves in sufficient large amount! "

towards infinity isn't having a problem for me, I'm not understanding why we need actually to determine the time complexity of algorithm in aspect of "sufficient largely" ?! thanks

 

Don't think of it telling you something about the algorithm "at infinity", but rather something about how the algorithm behaves for "sufficiently large" problems. How large is sufficiently large? That depends on the problem and the implementation of the algorithm. For some, anything over a data set consisting of 10 things might be large enough, while for others it might need to be 100,000 and for others even larger. In general, we don't know how big is big enough, so we look at the behavior as the problem size grows arbitrarily large (i.e., as the problem size goes towards infinity).

Actually lets assume a sufficient large number is 10^9 ..why if algorithm T(m) after 10^9 is faster than T(n) then we say T(m) is faster? May T(n) before 10^9 is faster than T(m)...why we are not determining it as faster so?

 

Another situation;
Lets assume I have two algorithms which T(m) is faster than T(n) over m=n=100, but at m,n > 100 the algorithm T(n) is faster than T(m) , so we determine than T(n) is faster .. but what about if the user's input m=n=100 then what I have given him (T(n)) isn't faster ! .. so how we make this decision although it's not obvious that the user's input would satisfy the algorithm's time complexity that I've given him? ( in this case I would give him T(m) because it's faster .. but we gave him T(n) ..so?! ))

 

towards infinity isn't having a problem for me, I'm not understanding why we need actually to determine the time complexity of algorithm in aspect of "sufficient largely" ?! thanks

Suppose a sorting algorithm has time complexity 0.001*n^4. For n <= 10 inputs, the algorithm is great! But after crossing the n > 10 threshold, it has dreadful performance. So, how do we classify it? One possibility is to call the algorithm sub-linear, and include a warning sticker that says USE ONLY ON INPUTS LESS THAN 10. But how generally useful is such an algorithm? Any of the standard sorting algorithms can sort 10 things in practically no time, and if the input size ever grows, they can handle it without requiring an expensive rewrite/test/update cycle.

To put it another way, imagine there is a car whose fuel efficiency is 200 miles per gallon for the first 100 feet of travel, which then degrades to 0.1 miles per gallon after that. Since most people expect to drive far more than 100 feet on a tank of fuel, we would consider it gross misrepresentation if the manufacturer claimed that their car had 200 mpg efficiency, even if they included a warning sticker saying to drive less than 100 feet.

We care about "sufficiently large" -- whether in terms of input size or miles driven -- because that's the more general case, having the widest applicability. Of course, there exist specific applications where we don't care about the general behavior of an algorithm, we only care about the fastest possible way that, for example, 4 sensor inputs can be sorted on this particular architecture. But that's a different goal from the categorization of algorithm complexity. In other words, when we're speaking generally, we care about "sufficiently large" because this captures the broadest sense of an algorithm's performance. On the other hand, when we're trying to optimize a specific application, we may care only about the exact performance details in that particular application. Two different goals with two different views of the factors involved.

 

my idea is "why actually we are looking to it as sufficiently large?" I don't have problem with the symbol infinity, but I meant that I have problem with the concept why we are looking to the problem how it behaves in sufficient large amount?!! "I'm not succeeding to understand the concept of why we need to look on time complexity of algorithm of how behaves in sufficient large amount! "

towards infinity isn't having a problem for me, I'm not understanding why we need actually to determine the time complexity of algorithm in aspect of "sufficient largely" ?! thanks

Because it's large problems that are the concern. If I'm trying to sort a list of 100 things, I don't really care whether the algorithm I use is n·log(n) or n² because, in either case, it will run fast enough that I probably won't notice the difference. But if I'm sorting a list of a million things I begin to care and if I'm sorting a list of a billion things I begin to care a lot.