Why is the time complexity of Tower of Hanoi with 4 pegs 0 (2^n/2)?

Question

For example if I use 4 disks, The problem should be solved in 3 steps according to the equation. However, mine takes 9 steps. Why is it so?

Consider the code here

include <stdio.h> 
void towerOfHanoi(int n, char from_rod, char to_rod,
                  char aux_rod1, char aux_rod2)
{
if (n == 0)
    return;
if (n == 1) {
    printf("\n Move disk %d from rod %c to rod %c",
                        n, from_rod, to_rod);
    return;
}

towerOfHanoi(n - 2, from_rod, aux_rod1, aux_rod2, 
                                        to_rod);
printf("\n Move disk %d from rod %c to rod %c ",
                   n - 1, from_rod, aux_rod2);
printf("\n Move disk %d from rod %c to rod %c ",
                      n, from_rod, to_rod);
printf("\n Move disk %d from rod %c to rod %c ", 
                   n - 1, aux_rod2, to_rod);
towerOfHanoi(n - 2, aux_rod1, to_rod, from_rod, 
                                    aux_rod2);
}

// driver program
int main()
{
    int n = 4; // Number of disks

    // A, B, C and D are names of rods
towerOfHanoi(n, 'A', 'D', 'B', 'C'); 
return 0;
}

Complexity O(2^n/2) does not mean that algorithm makes exactly 2^n/2 steps. Perhaps you need to read something like this: https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation — MBo, Apr 03 '18 at 07:12
The complexity is (2^N)/2, not 2^(N/2). So with 4 discs, that works out to 8 ... close enough to 9 for me. — Jim Mischel, Apr 03 '18 at 11:06
According to *what* equation? Most important, you *cannot* solve the problem if fewer moves than you have disks. You haven't given the equation you're using, merely the complexity. — Prune, Apr 03 '18 at 16:58
Also, note that 9 moves is the theoretical minimum for 4 disks on 4 pegs. You don't have a programming problem at this point. — Prune, Apr 03 '18 at 17:00
[Time complexity of tower of hanoi with 4 pegs ,similarly for 5 pegs it will be O(2^(n/3))](https://i.stack.imgur.com/sKcbX.jpg) — Rohit Kumar, Jul 11 '18 at 15:57

score 1 · Answer 1 · answered Jul 12 '18 at 13:01

When you have 4 pegs,time complexity to move 1 peg will require 1 comparison. time complexity to move 2 peg will require 3 comparisons. Time complexity = 2*T(n-2) + 3 ,n>=3

While solving it through substitution method . T(n) = 2*T(n-2) + 3 ,n>=3

= 2^2T(n-4) + 2*3 + 3 = 2^3T(n-6) + 2^2*3 + 2*3 + 3 and so on.

for kth substitution,

=2^(k/2)*T(n-k) + 2^(k/2 -1 )*3 + ..... + 2^2*3 + 2*3 + 3 ---- eqn_(1)

take n-k=2 => k=n-2 so eqn_(1) becomes = 2^(n/2 -1)*3 + 2^(n/2 - 2).3 + .....+ 2^2*3 + 2*3 + 3

= 3{1.(2^(n/2) - 1)}

= θ(2^(n/2))

Why is the time complexity of Tower of Hanoi with 4 pegs 0 (2^n/2)?

1 Answers1