1
$\begingroup$

I'm working through CLRS on problem 4-2, which says the following:

Throughout this book, we assume that parameter passing during procedure calls takes constant time, even if an $N$-element array is being passed. This assumption is valid in most systems because a pointer to the array is passed, not the array itself.

This problem examines the implications of three parameter-passing strategies:

  1. An array is passed by pointer. Time $ = \Theta (1)$.
  2. An array is passed by copying. Time $\Theta (N)$, where $N$ is the size of the array.
  3. An array is passed by copying only the subrange that might be accessed by the called procedure. Time $= \Theta(q-p+1)$ if the subarray $A[p \ldots q]$ is passed.

Consider the recursive merge sort algorithm. Give recurrences for the worst-case running times of binary search when arrays are passed using each of the three methods above, and give good upper bounds on the solutions of the recurrences. Let $N$ be the size of the original problem and $n$ be the size of a subproblem.

For part (2), one solution I have seen is:

$$T(n) = 2T(n/2) + cn + \color{red}{2N} = \color{blue}{4N} + cn + 2c(n/2) + 4T(n/4) = 8N + 2cn + 4c(n/4) + 8T(n/8) = \\ \qquad = \sum_{i=0}^{\lg{n}-1}(cn + 2^iN) = \sum_{i=0}^{\lg{n}-1}cn + N\sum_{i=0}^{\lg{n}-1}2^i = cn\lg{n} + N\frac{2^{\lg{n}} - 1}{2-1} = cn\lg{n} + nN - N = \Theta(nN) \\ \qquad = \Theta(n^2)$$

I don't understand where the $\color{red}{2N}$ has come from. The $2T(n/2)$ is the "conquer" part, and the $cn$ is the "combine" part, leaving the $\color{red}{2N}$ to be the "divide" part, but I'm not sure why it's $2N$ rather than just $N$, as you are only copying the $N$-length arrary over once.

Also, I don't understand where the $\color{blue}{4N}$ has come from (following the previous equality). Surely, $$T(n) = 2T(n/2) + cn +2N \\ = 2\underbrace{[2T(n/4) + c(n/2) + 2N ]}_{T(n/2)} + cn + 2N \\ = 4T(n/4) +2cn + 6N \ ?$$

Finally, am I right in thinking that the last equality holds because $N$ is some subset of $n$, so $n$ = $k N$ (for some constant $k$), so $T(n) = \Theta(n) \cdot \Theta(N) = n \cdot n = n^2$?

$\endgroup$
  • $\begingroup$ The question can't be answered without consulting the specific pseudocode. $\endgroup$ – Raphael Feb 1 '18 at 11:51
1
$\begingroup$

The $N$ is incurred once for every recursive call, since this is the cost of passing a parameter. Since there are two recursive calls, it's $2N$. As for the $4N$, this seems like a mistake. Don't expect solutions you find on the internet to be correct. Finally, $N$ is not a subset of $n$. It is the size of the original array. A less confusing way to write the conclusion would be $\Theta(nN) = \Theta(N^2)$. Note that it is always the case that $n \leq N$ (and not the other way around).

$\endgroup$
  • $\begingroup$ So are the two recursive calls the $D(n)$ part of $T(n) = aT(n/b)+C(n) + D(n)$? Also, should I replace $N$ with $n$, and $n$ with $N$ in my solution? $\endgroup$ – Spongebob Aug 5 '17 at 8:11
  • $\begingroup$ i.e. should it be $$T(N) = 2T(N/2) + cN + 2n \ ?$$ $\endgroup$ – Spongebob Aug 5 '17 at 8:13
  • $\begingroup$ No. You should think of $N$ as a constant, and of $n$ as a parameter, since $n$ keeps changing, while $N$ stays constant. $\endgroup$ – Yuval Filmus Aug 5 '17 at 9:09
0
$\begingroup$

I'm not sure how they got the $4N$ term either, but here's a simpler analysis. Let $T(n)$ be the cost of a recursive call of size $n$. We separate the costs of sorting, $S(n)$, and passing parameters, $P(n)$. We have:

  • $T(n) = S(n) + P(n)$
  • $S(n) = 2S(n/2) + cn$
  • $P(n) = 2P(n/2) + N$

Solving by standard methods yields $T(n) \in \Theta(n^2)$.

$\endgroup$
  • $\begingroup$ Why is $P(n)$ not just equal to $N$? Could you elaborate on "standard methods"? I can't use the master method because there are two recursive calls ($2S(n/2) $ and $2P(n/2)$) rather than one. $\endgroup$ – Spongebob Aug 5 '17 at 8:19
  • $\begingroup$ Also, I seem to be mixing up my $n$ and my $N$ terms. Can I write the whole thing as a function of $n$ only (or $N$ only)? $\endgroup$ – Spongebob Aug 5 '17 at 8:20
  • $\begingroup$ Why would it be equal to just $N$? It has recursive calls. Also, you would use the master theorem (or whatever else) on each recursive equation separately. And, no, you can't. $n$ and $N$ are different things. $\endgroup$ – quicksort Aug 5 '17 at 8:23
  • $\begingroup$ But that doesn't contradict the fact that it has recursive calls. If $T(n) = 2T(n/2) + cn + N$, then N is still going to increase with $n$, as $T(n/2)$ contains $N$. Also, you would eventually have that $T(n) = \Theta (nN)$ or something like that. How would you reason from this that $T(n) = \Theta(n^2)$? Finally, I just realised that $N$ is the size of the original problem and $n$ is the size of a subproblem. Shouldn't the recursions therefore be functions of $N$, rather than $n$ (i.e. $T(N) = \ldots $? I'm confused... $\endgroup$ – Spongebob Aug 5 '17 at 8:34
  • $\begingroup$ No, the recursions are functions of both $N$ and $n$. There isn't any problem with that. You would solve the $S$ and $P$ recursions separately and then add them. The $S$ part is $\Theta(n \log n)$ and the $P$ part is $\Theta(n^2)$, yielding quadratic complexity overall. $\endgroup$ – quicksort Aug 5 '17 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.