T(n) = 2T(n/2) + O(n)

T(n) = 2T(n/2) + a * n.
U(n) = T(2^n) とおく。log を 2 を底とする対数関数として、
T(n) = U(log n) = 2T(n/2) + a * n = 2U(log n - 1) + a * n.
N = log n とおくと、
U(N) = 2U(N-1) + a * 2^N.
両辺を 2^N で割ると
U(N)/2^N = U(N-1)/2^(N-1) + a.
よって、
U(N)/2^N = a N.
i.e. U(N) = a N * 2 ^ N.
N = log n. U(N) = T(n) より、
T(n) = a log n * n = O(n log n).

高校レベルの知識で解いたらこうなった