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$?

Improve this question
$\endgroup$
1
  • $\begingroup$ The question can't be answered without consulting the specific pseudocode. $\endgroup$ Commented Feb 1, 2018 at 11:51

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
3
  • $\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$ Commented Aug 5, 2017 at 8:11
  • $\begingroup$ i.e. should it be $$T(N) = 2T(N/2) + cN + 2n \ ?$$ $\endgroup$ Commented Aug 5, 2017 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$ Commented Aug 5, 2017 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)$.

Improve this answer
$\endgroup$
6
  • $\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$ Commented Aug 5, 2017 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$ Commented Aug 5, 2017 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$ Commented Aug 5, 2017 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$ Commented Aug 5, 2017 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$ Commented Aug 5, 2017 at 8:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.