Using the recursion tree method, we can see that the recursion tree will have log_2(n) levels, with each level containing nodes that sum up to n^2. Thus, the total cost of the algorithm will be the sum of n^2 at each level, which is:
T(n) = n^2 + (n/2)^2 + (n/4)^2 + ... + 1
This is a geometric series with a = n^2 and r = 1/4. The sum of the series is:
T(n) = n^2 * (1 - (1/4)^log_2(n+1)) / (1 - 1/4)
Simplifying the expression, we get:
T(n) = 4n^2 - n^2/(4^(log_2(n+1)))
Since 4^(log_2(n+1)) = (2^2)^(log_2(n+1)) = 2^(2log_2(n+1)) = 2^(log_2(n+1)^2) = (n+1)^2, we get:
T(n) = 4n^2 - n^2/(n+1)^2
Therefore, the asymptotic time complexity of T(n) is Θ(n^2).
