マスター定理、再発を解決する、T（N）= 3T（N/2）+ nlogn

Question

T（N）= 3 * T（N/2）+ N *ログ（n）は、その場合べき

適用され、なぜですか？私はケース1とは思うけど、確かではない。

マスター定理：

Answer 1

T(n) = 3 * T(n/2) + n * log(n) 

a = 3/b = 2/f(n) = n log n 

n^(log_b(a-ep)) = n^(log_2(3-ep)) = n^1.58... 

f(n) = n log n and is in O(n^1.58) as in case (1) 

Therefore, T(n) in Theta(n^1.58...)