T(N)을 크기가 N인 알고리즘을 수행할 때 걸리는 시간이라고 할 때, T(N)은 다음과 같은 recursive equation을 따른다.

T(N) = a*T(N/b) + c*N   ( a < b )

이 알고리즘의 asymptotic complexity를 big-O notation으로 나타내어라.


저는 이 문제를 이렇게 풀었습니다.

  T(1)= d, N=b^k라고 하자.

T(N) = T(b^k) = a*T(b^(k-1)) + c*N
                        = a(a*T(b^(k-2))+c*N) + c*N
                         = a^2 * T(b^(k-2)) + c*(1+a)
                         = ...
                         = a^k * T(1) + c*N (1+a+a^2+a^3+...+a^(k-1))
                         = a^(log_b N) + c/(a-1) * (a^(log_b N) - 1)

따라서 O(N * a^(log_b N)) = O(N^(1+log_b a))

  그런데 답은 O(N logN)이라고 합니다. 어디가 틀린건가요?