I understand how to compute the time complexity of the below formula by using Master Theorem:
$T[n]$ = $3T[\frac{n}{2}]$ + $n$
The answer is T(n) = $\Theta(n^{log_23})$
However, If I add a constant C in T(n), for example: $T[n]$ = $3T[\frac{n}{2} + C]$ + $n$, I cant apply that formula to the master theorem. And, I put the formula to the wolframalpha: the answer from wolframalpha
I figure out that the answer is not changed but I cant figure out why the result remain the same.
Thanks in advance
Let's look at the recursive expansion:
$n_1 = \frac{n}{2} + C = 0.5(n+2c)$
$n_2 = \frac{ 0.5(n+2c)}{2}+c = 0.25(n+ 2c+4c)$
$n_3 = \frac{0.25(n+2c+4c)}{2}+c = 0.125(n+2c+4c+8c)$
We can see where this is going.. so we can generalize this:
$n_k = \frac{1}{2^k} [n + c(2+4+ \dots 2^k)] = \frac{1}{2^k} [n + c(2^k -1)]$
We can check when this ends by solving for $n_k = 1$ or any other constant you would like (assuming this ends somewhere, meaning there is a value for $T[d] = \Theta(?) $ for $d \in \mathbb{N}$)
$$ \frac{1}{2^k} [n + c(2^k -1)] = 1$$
$$n + c \cdot 2^k - c = 2^k$$
$$2^k ( 1 - c) = n-c$$
Meaning that it would take us:
$$k = \log_2( \frac{n-c}{1-c}) = \log_2 (n-c) - \log_2(1-c) = \Theta( \log_2(n))$$
Steps to reach a constant value.
Keep in mind that we always multiply $T[f(n,c)]$ by 3 and add $n$ so we get:
$$ 3^{ \log_2 (n)} + n \cdot \log_2 (n)$$
$$ 3^{ \log_2(n)} = (2^{\log_2{3}})^{ \log_2 (n)} = n^{\log_2{3}}$$
And finally:
$$ n^{\log_2{3}} + n \cdot \log_2 (n) \in \Theta(n^{\log_2{3}})$$
(You can prove it with a limit or by finding $c_1, c_2$ etc..)