We were asked the to find the recurrence equation for the number of multiplications for the following algorithm as a function of N. For simiplicity, let $ N = 2^k $ and is a positive integer:
I understand that the the time for $T_1 = 0$ (Base Case) since there are no multiplications. For the recurrence part
$T_n = 2 + T_\frac{n}{2} + T_\frac{n}{2} = 2 + 2T_\frac{n}{2} $ because there a 2 recursive calls for every level before N == 1
Thereafter, I proceeded to expand:
$T_n = 2 + 2T_\frac{n}{2} $
$T_n = 2 + 2(2 +T_\frac{n}{2^2}) = 2 + 2^2+ 2T_\frac{n}{2^2}$
...
$T_n = 2 + 2^2 + 2^3 + ... + 2^k + 2^kT_\frac{n}{2^k} $
Since we could assume that $ n = 2^k $, the last term will be 0 since it would be $ T_1 $
Therefore the answer would be:
$T_n = 2 + 2^2 + 2^3 + ... + 2^k $ Which would have k number of terms, which could then simplified to $ T_n = 2^{k+2} - 2$ using Geometric Series.
However, the answer given to me was "There are k + 1 number of terms, which is simplified to $ T_n = 2^{k+1} - 2$
Why is this so ?
Thanks for your help!
$$2 + 2^2 + 2^3 + ... + 2^k= 2^{k+1} - 2\ne 2^{k+2} - 2$$