0
$\begingroup$

This question is from Exercise 1.7 in the book An Introduction to the Analysis of Algorithms by Robert Sedgewick and Kevin Wayne.

Assume that the running time of mergesort is $cN\lg{N}+ dN$, where $c$ and $d$ are machine-dependent constants. Show that if we implement the program on a particular machine and observe a running time $t_N$ for some value of $N$, then we can accurately estimate the running time for $2N$ by $2t_N(1 + 1/\lg{N})$ independent of the machine.

The following is my thought sketch:

Given the fact that $t_N = cN\lg{N} + dN$, then we have \begin{equation*} \begin{split} T_{2N} & = 2cN\lg{2N} + 2dN \\ & = 2cN(\lg{N} + 1) + 2dN \\ & = 2(cN\lg{N} + dN + cN) \\ & = 2(t_N + \frac{t_N - dN}{\lg{N}}) \\ & \approx 2(t_N + \frac{t_N}{\lg{N}}) \\ & = 2t_N(1 + 1/\lg{N}). \end{split} \end{equation*}

Is it safe to discard $-dN/\lg{N}$, and why?

$\endgroup$

2 Answers 2

0
$\begingroup$

$$\frac{t_{2N}}{2t_N}=\frac{2cN\lg(2N)+2dN}{2cN\lg(N)+2dN}=\frac{c\lg(N)+c+d}{c\lg(N)+d}=1+\frac1{\lg(N)+\dfrac dc}$$ and the claim seems wrong.


Assuming that $c=d$, for the error to be less than $1\%$, $N$ should be at least $2^{99}$ !

$\endgroup$
2
  • $\begingroup$ If we don't know the exact value of $d/c$, how can we accurately estimate the running time? $\endgroup$ Sep 4, 2023 at 14:17
  • $\begingroup$ @chenzhongpu: you have to determine it by fitting on several values of $(N, 2N)$. Anyway, notice that on modern machines the running times are non-deterministic and cannot be measured accurately anymore. $\endgroup$
    – user16034
    Sep 4, 2023 at 14:57
0
$\begingroup$

2 T(N) is exactly the time that you need to create two sorted subarrays of size N each from 2N items. Then you need to make one more pass to turn the two subarrays into one array. Since we need log(N) passes, one more pass is a factor (1 + 1 / log (N)).

In practice, this last pass is the pass that is most likely to exceed some cache limit, and therefore may run slower than other passes. Say you have 2MB of data and 1MB of fast cache. One half of the data is read from memory and sorted in the cache using maybe 15 passes, then that half is written back to memory, the other half is read and sorted in the cache. and then the last pass has to read and write two MB of memory, as much as the other 15 passes together.

$\endgroup$

Your Answer

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

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