재현식은

W(n) = 2W(2/n)+n-1         n>1        n=2^k(k>=1) 

이렇게 됩니다.

시간복잡도가 세타(nlgn) 인건 알고있는데 

어떻게 해서 이 값이 나오는지 궁금합니다.

책에서는 도사정리? 라는것을 쓰라고 나와있는데 그 도사정리라는것도 모르겠습니다

구글에 검색해도 자료가 나오지 않아 이렇게 도움 요청합니다.