하노이의 탑 관련된건데...
시간복잡도에 대한 분석들을 보면 대다수가 이렇게 되있더라구..
------------------------------------------------------------------
void dohanoi(int N, int from, int to, int using)
{ if (N > 0)
{ dohanoi(N-1, from, using, to);
 printf ("move %d --> %d\\n", from, to);
dohanoi(N-1, using, to, from); } }
-------------------------------------------------------------------------

<NOBR>T(n) = 2T(n-1)+1</NOBR>

<NOBR></NOBR> 

<NOBR>이렇게 됩니다 T(n)이 호출되면 우선 자신이 한번 수행되고 T(n-1)을 recursive하게 </NOBR>

<NOBR>두번 호출하기 때문이죠. </NOBR><NOBR>이 식을 풀어보면</NOBR>

<NOBR></NOBR> 

<NOBR>T(n) = 2T(n-1)+1</NOBR>

<NOBR>       = 2(2T(n-2)+1)+1</NOBR>

<NOBR>       = 2(2(T(n-3)+1)+1)+1</NOBR>

<NOBR></NOBR>  

<NOBR>즉  T(n) = 2^n - 1이 됩니다. 그래서 time complexity는 O(2^n)이 됩니다.