3 ms·

Out of curiosity, what line of work are you in given that you can seemingly pull this stuff from memory? All I read was "lorem ipsum..." until you got to Big O.

antics 12y ago
This is actually just standard theory. They teach this in every undergrad algorithms class. A lot of it is just getting good intuition for these sorts of problems. For example, the nth Fibonacci number has n log_2 \phi bits, which means that to simply list the digits in the nth number, it takes O(n) time. So from there it's pretty easy to see that actually this algorithm can't "really" operate in O(log n), or at least, something must be up that causes us to produce that analysis. Another bit of intuition that might help you see where this bound comes from: what's actually true is that it takes O(log n) _matrix multiplications_ to get the result. So if you see that and you see that listing the digits of the nth number of the sequence is O(n), it starts to point at the fact that there's a hidden cost to the multiplications.
phireal 12y ago
It's Colin Percival: author of tarsnap, former BSD security officer and considered something of an authority on crytography. I presume his maths skills are therefore suitably well polished to be able to pull this stuff from memory.
- antics 12y ago
  I want to dispel the rumor that this is magic. This is standard material in undergrad algorithms classes. See, for example, Jeff Erickson's algorithms notes here[1]. It's literally the first page of the chapter on dynamic programming. [1] http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf http://web.engr.illinois.edu/~jeffe/teaching/algorithms/note...
  - phireal 12y ago
    I appreciate that it's not magic and agree that it should be demystified. Having said that, doing it once in the past in an undergrad class and remembering it 10 years later when a relevant article on some website is posted are two different things.
  - raverbashing 12y ago
    Yeah, but "kids these days" only want to know Java or Angular.js and bawl at the first sight of math.
    - switz 12y ago
      Psh, who wants to learn Java?
      - lotyrin 12y ago
        I think "know" over "learn" used by the grandparent is important there; probably they were made to learn it for coursework, they want to be allowed to continue only having to know that much and not learn further.
- cperciva 12y ago
  More relevant than the above, my doctoral thesis was all about algorithms, and as an undergraduate student I published research in large integer arithmetic.
tomp 12y ago
He's in cryptography, he also started university at age 13. https://news.ycombinator.com/item?id=35076 https://news.ycombinator.com/item?id=35076

antics 12y ago

This is actually just standard theory. They teach this in every undergrad algorithms class. A lot of it is just getting good intuition for these sorts of problems. For example, the nth Fibonacci number has n log_2 \phi bits, which means that to simply list the digits in the nth number, it takes O(n) time. So from there it's pretty easy to see that actually this algorithm can't "really" operate in O(log n), or at least, something must be up that causes us to produce that analysis. Another bit of intuition that might help you see where this bound comes from: what's actually true is that it takes O(log n) _matrix multiplications_ to get the result. So if you see that and you see that listing the digits of the nth number of the sequence is O(n), it starts to point at the fact that there's a hidden cost to the multiplications.

phireal 12y ago

It's Colin Percival: author of tarsnap, former BSD security officer and considered something of an authority on crytography. I presume his maths skills are therefore suitably well polished to be able to pull this stuff from memory.

antics 12y ago
I want to dispel the rumor that this is magic. This is standard material in undergrad algorithms classes. See, for example, Jeff Erickson's algorithms notes here[1]. It's literally the first page of the chapter on dynamic programming. [1] http://web.engr.illinois.edu/~jeffe/teaching/algorithms/notes/05-dynprog.pdf http://web.engr.illinois.edu/~jeffe/teaching/algorithms/note...
- phireal 12y ago
  I appreciate that it's not magic and agree that it should be demystified. Having said that, doing it once in the past in an undergrad class and remembering it 10 years later when a relevant article on some website is posted are two different things.
- raverbashing 12y ago
  Yeah, but "kids these days" only want to know Java or Angular.js and bawl at the first sight of math.
  - switz 12y ago
    Psh, who wants to learn Java?
    - lotyrin 12y ago
      I think "know" over "learn" used by the grandparent is important there; probably they were made to learn it for coursework, they want to be allowed to continue only having to know that much and not learn further.
cperciva 12y ago
More relevant than the above, my doctoral thesis was all about algorithms, and as an undergraduate student I published research in large integer arithmetic.

tomp 12y ago

He's in cryptography, he also started university at age 13. https://news.ycombinator.com/item?id=35076 https://news.ycombinator.com/item?id=35076