I'm working on the problem from the Introduction to Algorithms book, where there is the following recurrence relation $T(n) = T(\frac{n}{2}) + \Theta(N)$, where $N$ is the size of the array we are searching for.
So the idea here is that on each level of the recursion we're copying each element of the initial array when passing it to solve a subproblem. I understand that the running time here is $\Theta(N\lg{N})$, because on each level we have to copy N elements which is $\Theta(N)$ and there are $\lg{N}$ such levels.
My question is can we apply the master theorem here? I tried to do this and either the theorem can't be applied here or I did something incorrectly. Here is my attempt:
For our recurrence we have $a = 1$, $b = 2$, $f(n) = \Theta(N)$, $N^{\log_b{a}} = N^{log_2{1}} = 1$. So we have that $f(n) = \Omega(1 * N^k)$, where $k = 1$. This is the third case, therefore we check the additional condition that $af(\frac{N}{b}) = \Theta(\frac{N}{2}) \le c \cdot \Theta(N) = \Theta(N)$, so that $c = 1$. So it seems that the solution can be $\Theta(N)$.
I understand that my solution via the master theorem is completely wrong and we probably can't use it to solve this recurrence, but I would like to understand why we can't and what's exactly wrong in my solution?
I'd be very grateful for any help or hints.
Best Answer
Notice $\Theta(N)$ is constant, so the inhomogeneous term, $f(n)$ in the theorem, is $O(n^0)$. The critical exponent is $\log_b a = 0$. This equals the power of $n$ in the inhomogeneous term, so you are in case 2.
In case 2, we write $f(n) = \Theta(n^0 \log^0 n)$. The result of the master theorem is $T(n) = \Theta(n^0 \log^1 n)$. Which is correct, you expect to get $\log_2 n$ copies of $\Theta(N)$.
Here's a potentially more useful way to approach this problem, that highlights more of the theory...
We don't actually have $T(n) = T(n/2) + \Theta(N)$ because that explicitly makes $T$ dependent on $n$ and $N$ (and two constants about which we will have more to say). So, really, we have $$ T(n,N) = T(n/2,N) + \Theta(N) \text{.} $$ That is, for each choice of $N$, there is a recurrence in $n$. If $N$ is chosen, we can suppress "$N$" in the recursive function $T$, which is what was done in the problem statement, but it is worth remembering that each choice of $N$ gives a different recursion. For each choice of $N$, we should think of this as an infinite list of facts: \begin{align*} T(2,N) &= T(1,N) + c(2,N) \text{,} \\ T(4,N) &= T(2,N) + c(4,N) \text{,} \\ T(6,N) &= T(3,N) + c(6,N) \text{,} \\ &\vdots \end{align*} We have some bounds on the $c$s and there are two forms these bounds can take.
Which of these two is the case, if it is established at all, is established prior to the portion of the problem statement that is recited in the Question. For our purposes, it doesn't actually matter which is the case, so we assume the latter. If the former is the case, then each of the functions $k_1$, $k_2$, and $n_0$ become constant functions.
So now we know: for each choice of $N$, we have an infinite list of recursion facts. Each of these has a $c(n,N)$ and those $c(n,N)$ are bounded below and bounded above by bounds that are independent of $n$. These bounds only depend on $N$. Once $N$ has been chose, the bounds on the $c(n,N)$ are fixed and have no dependence on $n$ -- every $c$ on the list has the same bounds. (It is a useful exercise to show that the $n_0$ in the definition of $\Theta$ used above can be reduced to $0$. The short version is that the finite beginning of the list with $n \leq n_0$ is automatically bounded by multiples of $N$ and then the infinite rest of the list is bounded by multiples of $N$. If you choose the looser of the lower bounds and the looser of the upper bounds, you have bounded the entire list by mutiples of $N$, so the whole sequence is $\Theta(N)$.)
Let's look at what happens when we don't choose $N$ but compute $T(8,N)$. \begin{align*} T(8,N) &= T(4,N) + c(8,N) \text{,} \\ &= T(2,N) + c(4,N) + c(8,N) \text{, and} \\ &= T(1,N) + c(2,N) + c(4,N) + c(8,N) \text{.} \\ \end{align*}
We know that \begin{align*} k_1(N) N &\leq c(2,N) \leq k_2(N) N \text{,} \\ k_1(N) N &\leq c(4,N) \leq k_2(N) N \text{, and } \\ k_1(N) N &\leq c(8,N) \leq k_2(N) N \text{.} \end{align*} From these, $$ 3 k_1(N) N \leq c(2,N) + c(4,N) + c(8,N) \leq 3 k_2(N) N \text{.} $$ (This inequality is what we mean when we write "$3\Theta(N)$" -- the sum of three, likely different, bounded numbers.)
Notice that the bounds on $c$ are independent of $n$. Whether $n$ is big or small, $c$ has the same bounds, so $\Theta(N)$ is both notationally and actually independent of $n$. That means $\Theta(N) \in O(n^0)$ (relative to $n$).
When we choose an $N$ and apply the master theorem to $T(n)$ (with the dependence on $N$ suppressed because we have already chosen $N$), we treat $n$ as the independent variable. Consequently, $\Theta$ and $O$ are relative to $n$. As we have shown $\Theta(N)$ is independent of $n$ -- the upper and lower bounds implicit in "$\Theta(N)$" are independent of $n$. We may replace $\Theta(N)$ with either the constant $k_1(N)N$ or the constant $k_2(N)N$, whichever leads to the worst case, and apply the master theorem to this recursion with constant inhomogeneous term. The result is described in the very first part of this Answer.