algorithm - Solving T(n)=4T(n/2)+n^2 - Stack Overflow

algorithm - Solving T(n)=4T(n/2)+n^2 - Stack Overflow

T(n)=4T(n/2)+n² = n²+4[4T(n/4)+n^2/4] = 2n²+16T(n/4) = ... = k*n²+4^kT(n/2^k) = ...

The process stops when 2^k reaches n. ==> k = log₂n.

==> T(n) = O(n²logn).

Read full article from algorithm - Solving T(n)=4T(n/2)+n^2 - Stack Overflow