using the master theorem solve the following recurrence rela

using the master theorem, solve the following recurrence relation:
T(N)= 2T(N/4)+N
with T(2)=1

Solution

According to master therom

T(N) = aT(N/b) + N

Comparing the equation

T(N)= 2T(N/4)+N

a = 2

b = 4

In first equation let us put n = n/4

T(N/4) = 2T(N/16 + N/4) + N/4

and so on we will end with a recurrence and final answwer is:

(N²)