Perl: the Markov chain saw  
PerlMonks 
Comment on 
( #3333=superdoc: print w/replies, xml )  Need Help?? 
(If you're not interested in computer science subtleties, please ignore this node  for normal programming tasks the O(1) estimate is good). For big numbers the algorithm is slower than O(n), while the summing all the values is O(2^n). In computer science, if you are talking about O(f(n)), n is the input length, not the number that the input presents. So adding two numbers with length n is O(n), multiplying two numbers naively is O(n^2), there are a few more elaborate algorithms that do it a bit faster. Summing all numbers from 1 to $number is O(2^n), because the length of $number is what we call n. (This calculation kinda assumes use bigint;, because otherwise on the perl vm adding and multiplying is O(1) indeed) In reply to Re^3: beginner help
by moritz

