how do i solve for running time in the towers of Hanoi problem. I get a recurrence realation like t(n) = 2t(n-1) + 1. After drawing the recursion tree i get at every step values like 1+2+4+8... the height of the tree will be lg(n). how do i calculate the sum of the series? when do i stop?
+2
A:
Did you checked http://en.wikipedia.org/wiki/Tower_of_Hanoi? You have everything in there.
Parkyprg
2010-09-28 14:05:43
really? you think I don't know how to use the internet
2010-09-28 14:15:50
@user265260: You never specified. Don't get snarky at answers given because your question wasn't well-stated.
Daenyth
2010-09-28 14:17:11
@user265260: apparently you hadn't looked at the wikipedia article, because the answer to your question is in there.
LarsH
2010-09-29 02:08:45
+6
A:
What you get at each level of the recursion tree is a power of 2. Hence, the sum is: 2^0 + 2^1 + 2^2 + ... + 2^{n-1}.
That's a geometric sum: http://en.wikipedia.org/wiki/Geometric_progression
Let S(n) = 1 + 2 + 4 + ... + 2^{n-1}. Then: S(n) - 2*S(n) = 1 - 2^n
And finally: S(n) = 2^n - 1.
Sheldon L. Cooper
2010-09-28 14:07:31
You can find that out by trying with small cases. For `n = 1` you get `2^0`. For `n = 2`, `2^0 + 2^1`. So the highest exponent is `n-1`, not `n`.
Sheldon L. Cooper
2010-09-28 14:21:27
@user265260: Mr. Cooper has the correct sum. Think of it this way: what is the largest value an unsigned integer with n bits can represent? That is different than the number of values that n bits can represent since 0 is one of those values.
andand
2010-09-28 14:23:01