I wrote this as a comment there, but I'll repaste it here since it's not showing up. ----------- One other thing I'd like to add, when considering asymptotic

I wrote this as a comment there, but I'll repaste it here since it's not showing up. ----------- One other thing I'd like to add, when considering asymptotic analysis, one needs to take into account both the cost model (i.e. what is assumed about the cost of operations) and the input size (i.e. what the variables mean). So for instance, if I tell you that the following program to find a number's divisors is O(n) operations, I wouldn't necessarily be wrong: for(i = 1; i <= n; ++i) if(n % i == 0) printf("%d\n", i); After all, this is doing a single loop, and it will loop exactly n times. So why isn't factoring a solved problem? We can factor numbers "in polynomial time!", I'll just check this list! Factoring, as a problem, is measured using bit complexity. That is, the input size is the number of bits needed to store the number I want to factor. So my program is actually O(2^m) operations, where m is the input size. And so this isn't factoring "in linear time", I just misunderstood what the input size was. Likewise, one can do analyses where the operation cost (also called computational model) is different from the uniform model. If I am doing crypto, using GMP, it would not be smart to say that adding any two GMP integers is O(1) operations, like we assume with our standard model of costs, where adding integers is O(1). We can certainly assume that, and call that a basic operation, but we will see the number of operations and time it takes to be wildly different, so one should use an analysis where the cost of adding, say, the numbers n and m, is O(log n + log m) operations for instance, if one wants operation-counting analyses to give a hint at runtime. It is important to remember that it is the analyst who defines what operations are basic, and one can do analysis of the same algorithm in different cost models, to get different information about it. So asymptotic analyses of algorithms depend on both the input size, and the cost model. My divisors finding algorithm, for instance, is best measured using the logarithmic model of computation, and logarithmic input size. As a trick, it's fun to try to construct two functions f:N -> N, g:N -> N, such that neither f is O(g), nor g is O(f). Bonus points if they're both monotonically increasing. :) It's useful to dispel the notion that functions are given a total order by big-O notation.