3
$\begingroup$

The exercise gave us a chart which showed the running time as a $N$ increases:

\begin{array}{c|c} N & \text{seconds}\\\hline 256 & 0.000\\ 512 & 0.000\\ 1024 & 0.002\\ 2048 & 0.009\\ 4096 & 0.042\\ 8192 & 0.175\\ 16384 & 0.788\\ 32768 & 3.440\\ 65536 & 15.010\\ 131072 & 65.873\\ 262144 & 290.449\\ 524288 & 1272.816\\ \end{array}

My process was to use the power law to figure out the growth of the running time.

$$T(n)=aN^b$$

I divided the seconds and figured out that as $N$ doubles the running time quadruples, indicating a quadratic growth rate or $b=2$. So then I simply put in $1272.816$ as $T(n)$ and $2$ for $b$ and solved for $a$:

\begin{align*} T(n)&=aN^b\\ 1272.816 &= a 524288^2\\ a &= \frac{1272.816}{524288^2}\\ a &= 4.630 \cdot 10^{-9} \end{align*}

It turns out my answer was wrong when I looked at the answer. The actual answer computed the ratio and the used the $\log_2$ of that ratio to determine where the running time converges:

The theoretical order-of-growth is $N^\left(\frac{32}{15}\right) = 2.13$

The empirical order-of-growth is $N^{\log_2 \text{ratio}}$

\begin{array}{c|c} N & \text{seconds} & \text{ratio} & \log_2\text{ratio}\\\hline 256 & 0.000 & - & -\\ 512 & 0.000 & - & -\\ 1024 & 0.002 & - & -\\ 2048 & 0.009 & 4.50 & 2.17\\ 4096 & 0.042 & 4.67 & 2.22\\ 8192 & 0.175 & 4.17 & 2.06\\ 16384 & 0.788 & 4.50 & 2.17\\ 32768 & 3.440 & 4.37 & 2.13\\ 65536 & 15.010 & 4.36 & 2.13\\ 131072 & 65.873 & 4.39 & 2.13\\ 262144 & 290.449 & 4.41 & 2.14\\ 524288 & 1272.816 & 4.38 & 2.13\\ \end{array}

I'm not sure how they got the ratio. In the video the instructor said to double the input $N$ and compute the ratio of the running time of $N$ and $2N$. Looking at the $\log_2$ tells us what $b$ is.

Here are my questions:

  • How did they determine the theoretical and empirical growth order?
  • Can you give a step by step instruction on how to get the ratio?
$\endgroup$
2
$\begingroup$

The ratios are simply computed as the name suggest (provided the time values are non-zero):

      0.009/0.002 = 4.5000    log2(0.009/0.002) =  2.1699
      0.042/0.009 = 4.6667    log2(0.042/0.009) =  2.2224
      0.175/0.042 = 4.1667    log2(0.175/0.042) =  2.0588
                  ...                          ...
   290.449/65.873 = 4.4092    log2(...)         =  2.1405
 1272.816/290.449 = 4.3822    log2(...)         =  2.1316

I give four decimal digits, in your source the values are rounded to two digits. The empirical growth rate is just the limit (or the best fit, or mean of the last, or ...) of the log2(ratio) values. $32/15\;$ is just a good approximation to 2.13, but IMO a theoretical growth rate is somewhat meaningless without a theory behind the process.

$\endgroup$
  • $\begingroup$ So where does the power law come into this? I saw it being used to solve a similar problem in the lectures. $\endgroup$ – user6607 Sep 18 '14 at 12:29
  • $\begingroup$ @user6607: I don't know. As I have written, you gave no description of what is timed. There are many algorithms which have a complexity of $O(N^2)\;$ e.g. some sorting algorithms, school-book multiplication of large integers etc. $\endgroup$ – gammatester Sep 18 '14 at 12:35
  • $\begingroup$ Yeah the exercise doesn't tell us much about what is being timed either: Suppose that you time a program as a function of N and produce the following table. Estimate the order of growth of the running time as a function of N. Assume that the running time obeys a power law T(N) ~ a N^b. $\endgroup$ – user6607 Sep 18 '14 at 12:43
  • $\begingroup$ @user6607: Generally you can use power laws for processes where the logarithms of the variables show a linear dependency $\ln y = a \ln x,\;$ or when the relative changes are proportional $$\frac{\Delta y}{y} = a \frac{\Delta x}{x}\approx\frac{dy}{y} = a \frac{dx}{x} \Longrightarrow y(x) = b x^a$$ $\endgroup$ – gammatester Sep 18 '14 at 12:55

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.