Answer:
We will use the substitution method to find the solution of the recurrence equation T(n) = 16T(n/4) + √n.
Let us assume that the solution of this recurrence equation is T(n) = O(n^(log_4 16)).
Now, we need to show that T(n) = Ω(n^(log_4 16)) and thus T(n) = Θ(n^(log_4 16)).
Using the given recurrence equation:
T(n) = 16T(n/4) + √n
= 16 [O((n/4)^(log_4 16))] + √n (using the assumption of T(n))
= 16 (n/4)^2 + √n
= 4n^2 + √n
Now, we need to find a constant c such that T(n) >= cn^(log_4 16).
Let c = 1.
T(n) = 4n^2 + √n
= n^(log_4 16) (for sufficiently large n)
Hence, T(n) = Ω(n^(log_4 16)).
Therefore, T(n) = Θ(n^(log_4 16)) is the solution of the given recurrence equation T(n) = 16T(n/4) + √n.
Step-by-step explanation: