If you were to solve the Towers of Hanoi puzzle recursively by moving n - 1 smallest disks to the second rod, moving the largest disk, then recursively moving the stack from the second rod on top of the largest, you get the recurrence relation: $T(n) = 2T(n - 1) + 1$. So, let's say $S(n) = T(log_2n)$. How could I use this to write a recurrence relation for $S(n)$? As of right now I have: $$S(n) = 2T(log_2n - 1) + 1 = 2T(log_2n-log_22) + 1 = 2T(log_2(\frac{n}{2})) + 1$$ Not really sure if I'm going the right way with this, but I'm not sure where to go after this. After solving for a recurrence relation for $S(n)$, how could we use this to find an asymptotic expression for $T(n)$ using Big-O notation?

  • $\begingroup$ $2T(\log_{2}(\frac{n}{2})) = 2S(\frac{n}{2})$ $\endgroup$ – Matija Sreckovic Jan 15 '18 at 18:51
  • $\begingroup$ How did you get that? $\endgroup$ – A. L. Jan 15 '18 at 18:53
  • $\begingroup$ If $S(n) = T(\log_{2}(n))$, then $S(\frac{n}{2}) = T(\log_{2}(\frac{n}{2}))$. $\endgroup$ – Matija Sreckovic Jan 15 '18 at 18:54
  • $\begingroup$ So then the recurrence for $S(n)$ would be $S(n) = 2S(\frac{n}{2}) + 1$? And this would have a asymptotic complexity of $O(n)$? How could I use this to find a Big-O complexity for $T(n)$? $\endgroup$ – A. L. Jan 15 '18 at 19:13
  • $\begingroup$ I'm not really good at proving $O$'s formally, but here's an intuitive approach: if you have a number $n$, and you want to keep dividing it by $2$ until you get $1$, you'll have to do it around $\log_{2}n$ times. So the asymptotic complexity of $S$ would be about $2 \times 2 \times 2... \times 2$, $\log_{2}n$ times, so it's about $2^{\log_{2}n} = n$ (if you ignore the $+1$'s). What happens to the $1$'s? Hint: how much is $1+2+...+2^k$? $\endgroup$ – Matija Sreckovic Jan 15 '18 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.