0
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

  • There are (universal) contants, $k_1 > 0$, $k_2 > 0$, and $n_0 > 0$ such that for all $n > n_0, $ $$ k_1 N \leq c(n,N) \leq k_2 N \text{.} $$
  • For each choice of $N$, there are constants (where we do not suppress the dependence on $N$) $k_1(N) > 0$, $k_2(N) > 0$, and $n_0(N) > 0$ such that for all $n > n_0$ $$ k_1(N) N \leq c(n,N) \leq k_2(N) N \text{.} $$

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.

$\endgroup$
7
  • $\begingroup$ Thank you for the answer, but I still have difficulties with some points. You're saying that $\Theta(N)$ is constant because on each level of the recursion it remains the same? But it still depends on the input size (array size actually), so why we can say that $f(n) = O(1)$? And $n^0$ is $1$, right? Why we can say that $\Theta(n^0 \log{n})$ is the same as $\Theta(n \log{n})$? And what do you mean by $\log_2{n}$ copies of $\lg{N}$? In fact, we have $\lg{N}$ copies of $N$. I'm very sorry if I misunderstood something, probably it's too advanced math for me :( $\endgroup$ Commented Feb 18, 2021 at 21:04
  • $\begingroup$ @E.Shcherbo : The form in the master theorem is $T(n) = a T(n/b) + f(n)$. $\lg N$ does not depend on $n$ because $n$ varies as you proceed through the recursive evaluation, but $N$ does not. Therefore, $f(n) = \lg N$ sets $f(n)$ to a constant, an expression independent of $n$. (For the entire recursion, $\lg N$ is the same everywhere it appears but $\lg n$ is not.) $\endgroup$ Commented Feb 19, 2021 at 0:13
  • $\begingroup$ @E.Shcherbo : We do not say $\Theta(n^0 \log n)$ is the same as $\Theta(n \log n)$. Anywhere. $n^0 \log^0 n = 1$, so we are saying that $f(n)$ is constant. When I say "$\log_2 n$" copies of $\lg N$, I mean that literally, when you evaluate $T(n)$. Try it with $T(8) = T(4) + \lg N = T(2) + 2 \lg N = T(1) + 3 \lg N$. We're down to the base case and have accumulated three copies of $\lg N$. $\endgroup$ Commented Feb 19, 2021 at 0:15
  • $\begingroup$ Why $T(8)=T(4)+\lg{N}$ if it should be $T(8) + T(4) + \Theta(N)$ or $T(8) + T(4) + cN$ for some constant $c$? Did I understand something wrong? $\endgroup$ Commented Feb 19, 2021 at 19:27
  • $\begingroup$ @E.Shcherbo : Oops! Miscopied. $T(8) = T(4) + \Theta(N) =$ $T(2) + 2\Theta(N) =$ $T(1) + 3\Theta(N)$. So we get $\lg n$ copies of $\Theta(N)$ (fixed in Answer as well). $\endgroup$ Commented Feb 19, 2021 at 21:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .