Question Hanoi complexity

Master / Vertiefung Künstliche Intelligenz
1

Goto Betreff

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Question Hanoi complexity
Hi,

I just finished programming the Towers of Hanoi an was wondering, what to do in the next Exercise:
“Determine the complexity class of your algorithm and explain how you computed it”

For the complexity class: What is wanted here? Shall i say, that it’s in P, NP, etc? Or shall i say, it is computed with O(…).
My second question is, how do i say explain, how it is computed? Shall i say, what every line of code dose, e.g. commenting every line, or shall i say, how it can be solved by hand?
(Sorry for my bad english)

3

First, let’s distinguish here between the complexity of a (decision, search) problem and the complexity of a given algorithm. There may be many algorithms for the same problem and they may all have different complexity. As opposed to this the complexity class of the problem tells you which kinds of algorithms can solve the problem. For example, when a problem is in P, then there exists a deterministic algorithm to solve it in polynomial time. If it is in EXP, then there exists a deterministic exponential time algorithm that solves it (if it is EXP-hard, then there exist only at least exponential time deterministic algorithms for it).

Here you are ask to assess the complexity of the specific algorithm you implemented. So up to O(…), give the number of steps your algorithm needs to solve the problem.

You are supposed to explain how you compute the algorithm’s complexity. But yes, you should definitely also comment your code.

Come to my tutorial tomorrow (Tuesday) morning at 8.15 for an example.

4

A little more concretely, there is a slide in the notes “Recap: Time/Space Complexity of Algorithms” with some common Launday sets / complexity classes. You should say which one of these the Hanoi solution falls into, and explain why that is so (no need to prove it mathematically).