The Tower of Hanoi and Big O notation
I very much enjoyed the story of the great mathematician Gauss who as an elementary student in late 18th Century was asked with the rest of the class to count the sum of the integers from 1-100. Within ten minutes a little chap at the back of the class put his hand up with the answer: 5, 050. Gauss had discovered that the formula for the sum of the first n integers was 1/2 n (n + 1). So the answer for the sum of integers from 1–100 was 50 x 101 (the sum of each pair) = 5, 050.
The tower of Hanoi was quite different but also represented a series of actions which could be rationalised. The objective in the game was to move the disks from peg A to peg C in such a way that they were in the same order with biggest at the bottom. How could I solve this?
First I had to ensure that I understood the problem. The first step was to move the top disks from the beginning to the auxiliary peg. The second step to move one disk from the beginning to the end peg. The third step was to move the top disk from auxiliary to the end disk. It turned out that if there are N disks then I could solve the game in minimum:
For example if there are three disks the minimum moves required are:
2³ -1 = 7
In Ruby this translated to the more attractive and simple:
So far so good but it turns out that this recursive function can lead to questions regarding optimum performance or complexity of an algorithm. Big O describes the worst case scenario in terms of time or space required by an algorithm. The list of options are:
O (1): this algorithm will always execute in the same time regardless of the size of the input set.
O(N) describes an algorithm whose performance will grow linearly in direct proportion to the size of the data set.
O(N²) represents an algorithm whose performance is proportional to the square of the size of the data set.
O (2^N) denotes an algorithm whose growth doubles with each addition to the data set.