Skip to content

4-2 Parameter-passing costs

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. Arrays are passed by pointer. Time $= \Theta(1)$.

  2. Arrays are passed by copying. Time $=\Theta(N)$, where $N$ is the size of the array.

  3. Arrays are passed by copying only the subrange that might be accessed by the called procedure. Time $=\Theta(n)$ if the subarray contains $n$ elements.

Consider the following three algorithms:

a. The recursive binary-search algorithm for finding a number in a sorted array(see Exercise 2.3-6).

b. The MERGE-SORT procedure from Section 2.3.1.

c. The MATRIX-MULTIPLY-RECURSIVE procedure from Section 4.1.

Give nine recurrences $T_{a1}(N,n),T_{a2}(N,n),\dots ,T_{c3}(T,n)$ for the worst-case running times of each of the three algorithms above when arrays and matrices are passed using each of the three parameter-passing strategies above. Solve your recurrences, giving tight asymptotic bounds.

a

a1

$$ \begin{aligned} T_{a1}(N,n)=T(N,\frac{n}{2})+\Theta(1)\cr n^{\log_{b}a}=n^{\log_{2}1}=1\cr f(n)=\Theta(1)=\Theta(n^{\log_{b}a})\cr T_{a1}(N,n)=\Theta(\lg n)\cr \end{aligned} $$

a2

$$ \begin{aligned} T_{a2}(N,n)=T(N,\frac{n}{2})+\Theta(N)\cr n^{\log_{b}a}=n^{\log_{2}1}=1\cr T_{a2}(N,n)=\Theta(N\lg n)\cr \end{aligned} $$

a3

$$ \begin{aligned} T_{a3}(N,n)=T(N,\frac{n}{2})+\Theta(n)\cr n^{\log_{b}a}=n^{\log_{2}1}=1\cr f(n)=\Theta(n)=\Omega(n^{1+\log_{b}a})\cr af(\frac{n}{b})=f(\frac{n}{2})\leq \frac{1}{2}f(n)\cr T_{a3}(N,n)=\Theta(f(n))=\Theta(n)\cr \end{aligned} $$

b

b1

$$ \begin{aligned} T_{b1}(N,n)=2T(N,\frac{n}{2})+\Theta(n)\cr n^{\log_{b}a}=n^{\log_{2}2}=n\cr f(n)=\Theta(n)=\Theta(n^{\log_{b}a}\lg^{0}n)\cr T_{b1}(N,n)=\Theta(n \lg n)\cr \end{aligned} $$

b2

$$ \begin{aligned} T_{b2}(N,n)=2T(N,\frac{n}{2})+\Theta(N+n)=2T(N,\frac{n}{2})+\Theta(N)\cr n^{\log_{b}a}=n^{\log_{2}1}=n\cr T_{b2}(N,n)=\Theta(n+N\lg n)=\Theta(N\lg n)\cr \end{aligned} $$

b3

$$ \begin{aligned} T_{b3}(N,n)=2T(N,\frac{n}{2})+\Theta(n)\cr n^{\log_{b}a}=n^{\log_{2}2}=n\cr f(n)=\Theta(n)=\Theta(n^{\log_{b}a}\lg^{0}n)\cr T_{b3}(N,n)=\Theta(n \lg n)\cr \end{aligned} $$

c

c1

$$ \begin{aligned} T_{c1}(N,n)=8T(N,\frac{n}{2})+\Theta(1)\cr n^{\log_{b}a}=n^{\log_{2}8}=n^3\cr f(n)=\Theta(1)=O(n^{\log_{b}a-3})\cr T_{c1}(N,n)=\Theta(n^3)\cr \end{aligned} $$

c2

$$ \begin{aligned} T_{c2}(N,n)=8T(N,\frac{n}{2})+\Theta(N)\cr n^{\log_{b}a}=n^{\log_{2}8}=n^3\cr T_{c2}(N,n)=\Theta(n^3+N\lg N)\cr \end{aligned} $$

c3

$$ \begin{aligned} T_{c3}(N,n)=8T(N,\frac{n}{2})+\Theta(n)\cr n^{\log_{b}a}=n^{\log_{2}8}=n^3\cr f(n)=\Theta(n)=O(n^{\log_{b}a-2})\cr T_{c3}(N,n)=\Theta(n^3)\cr \end{aligned} $$