Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re^2: beginner help

by jeffa (Chancellor)
on Aug 02, 2010 at 20:49 UTC ( #852537=note: print w/ replies, xml ) Need Help??


in reply to Re: beginner help
in thread beginner help

O(1) for the win. :)


jeffa

L-LL-L--L-LL-L--L-LL-L--
-R--R-RR-R--R-RR-R--R-RR
B--B--B--B--B--B--B--B--
H---H---H---H---H---H---
(the triplet paradiddle with high-hat)


Comment on Re^2: beginner help
Select or Download Code
Re^3: beginner help
by moritz (Cardinal) on Aug 03, 2010 at 07:44 UTC

    (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)

      What is the "n" depends. It could very well be the output length, if the task at hand was eg. to produce N random numbers where N is the number coming from the input. There the length of the input is not really interesting, the value is. (OK, the length and the value of the number is kinda related, but you know what I mean.

      Jenda
      Enoch was right!
      Enjoy the last years of Rome.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://852537]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (14)
As of 2014-07-14 12:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    When choosing user names for websites, I prefer to use:








    Results (259 votes), past polls