Need some help with exam

[fiskpatte]

Hi. A question that is always present on our exams is about the Tower of Hanoi ( http://en.wikipedia.org/wiki/Tower_of_Hanoi ) .

It takes (2^n)+1 moves to move all the discs, where n is the number of discs.
The question is to give the answer in Θ-notation. According to me, the answer should be Θ(2^n).
Am I correct?

best regars // Pontus

[Zachm]

As I remember, the number of moves required is (2^n) - 1,
anyhow, this number is Theta(2^n) if and only if it's O(2^n) and also Omega(2^n).

Go back to the mathematical definition of the big-Oh and big Omega notations to see if it is so.

Regards,
Zachm