I am trying to solve the following $T(n) = 4T(n/2) + p*n $ where p is a constant, we may assume $ n = 2^k $
I took the general equation as $T(n) = a*T(n/b) + g(n) $ Writing it recursively i came to the following function: assuming i as the tree depth, first one is i = 1 listed above
$T(n) = a^i*T(n/b^i) + \sum\limits_{k=0}^{i-1} a^k*g(n/b^k) $
so substituting the above equation we get:
$T(n) = 4^i*T(n/2^i) + p\sum\limits_{k=0}^{i-1} 4^k*(n/2^k) $
$T(n) = 4^i*T(n/2^i) + p\sum\limits_{k=0}^{i-1} 2^k*n $
since the base case $ T(1) = constant $, then we can say $1 = (n/2^i)$ taking log of both side $log(2^i) = log(n)$ thus $ i = log_{2}(n) $
putting it back into the equation we get:
$T(n) = 4^{log_{2}(n)}*T(n/2^{log_{2}(n)}) + p\sum\limits_{k=0}^{log_{2}(n)-1} 2^k*n $ simplifying it $T(n) = n^{2}*T(1) + p\sum\limits_{k=0}^{log_{2}(n)-1} 2^k*n $
since it says we may assume that $ n = 2^k $, if i put that into the equation: $T(n) = n^{2}*T(1) + p\sum\limits_{k=0}^{log_{2}(n)-1} n*n $, which in turn comes to: $T(n) = n^{2}*T(1) + p*n^2\sum\limits_{k=0}^{log_{2}(n)-1} 1 $, which comes to: $T(n) = n^{2}*T(1) + p*n^{2}*log_{2}(n) $ from this it looks as if $ p*n^{2}*log_{2}(n) $ is the dominant term, thus it comes to $ O(n) = n^{2}*log_{2}(n) $, but according to the master theorem this should be $ O(n) = n^{2} $, i am not quite sure where i am making the mistake here. Help is really appreciated.
You have used $k$ in two different places. Firstly, to say that $n$ is a power of 2, you say $n=2^k$. Secondly, you use $k$ as the dummy variable to sum all the smaller powers.
In most of your calculations, $n=2^i$. When you write "since it says we may assume $n=2^k$", you should have written $n=2^i$ instead.
Do you know what the sum $\sum_{k=0}^{i-1}2^k=1+2+...+2^{i-1}$ equals?