Comparing timing between algorithms (Big O) [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

If a program can solve the towers of Hanoi problem for 30 disks in 1 minute, how long would it take to solve the problem with 24 disks? How about 60 disks?

I know you need to figure out some sort of formula in order to work this out but how is that done? Thank you!

Answer 1

It depends on the actual complexity. Without knowing that, all you can say is that it will generally take more than one minute to shift 60 disks and less to shift 24 :-)

As it happens, the complexity for Hanoi is basically O(2n). The reason for that is that if it takes x operations to shift 30 disks from pole A to pole C, it will basically take 2x operations to shift 31.

The reasoning behind that is that you use x operations to shift the first 30 disks from A to B, then shift the biggest disk from A to C, then use another x operations to shift everything from B to C.

So, in it's purest form, it would take 1/2 x 1/2 x 1/2 x 1/2 x 1/2 x 1/2 x 1 minute to shift 24 disks (1/2 for each of the six steps from 30 down to 24), or just under a second.

For 60 disks, that would be 230 x 1 minute, or about two thousand years.

---

Keep in mind that complexity analysis isn't really meant to tell you how long something will take but rather how the effort (such as processing step counts) changes as the input size changes.

Generally, you only use the term that's most significant as the input size increases, so that the formulae showing processing step counts of:

2^n + n^2
2^n - 42
2^n + n^2 + 7n + 12

would all be considered O(2n) as that's the most important term.

The time taken will be affected by all terms. The "purest form" I refer to above is meant to indicate that the complexity is the only term that affects running time.