“The greatest shortcoming of the human race is our inability to understand the exponential function.”
Albert Allen Bartlett
These are depressing times so this month’s contribution (a bit short for time, to be honest), though topically linked to the ongoing pandemic, deserves attention from different angles in its own right.
We’re going to have a quick look at exponential growth.
2 Comments | tags: Exponential complexity | posted in Computer Science, General, Hardware, Mathematics
(A case study in bad and good algorithm design. Hopefully, a bit of fun for anyone in a programming frame of mind, but also serving as a useful reference for the ‘Are There Any Hard Problems?’ post that follows.)
In ‘A Scandal in Bohemia‘ (Arthur Conan Doyle, 1891), Holmes and Watson discuss the difference between seeing and observing: “You see, but you do not observe [Watson]. The distinction is clear. For example, you have frequently seen the steps which lead up from the hall to this room.” “Frequently.” “How often?” “Well, some hundreds of times.” “Then how many are there?” “How many? I don’t know.” “Quite so! You have not observed. And yet you have seen. That is just my point. Now, I know that there are seventeen steps, because I have both seen and observed.”
Who knows; perhaps, if they hadn’t moved on to discuss more pressing issues (that King of Bohemia has a lot to answer for), Holmes may have set Watson something a little more interesting: “How many of these steps do you generally take in a single stride, Watson?” “I suppose one or two, Holmes, it varies; never three. Sometimes I take different combinations of one and two steps as the mood takes me” “Excellent, Watson; another challenge! So, taking these steps one or two at a time, in any combination you wish, how many different ways are there of climbing the seventeen steps?” “Well, I’m quite sure I don’t know, Holmes; rather a lot, I would imagine!” Continue reading
9 Comments | tags: Complexity, Exponential complexity, Fibonacci Sequence, Iteration, Program design, Recurrence relation, Recursion, Recursive definition, Software efficiency | posted in Academia, Algorithms, Computer Science, Computing, Mathematics, Programming, Software