[Math] Time complexity – Doubling the speed of a machine that uses a O(N Log N) algorithm

computational complexity

Related to this question: Time complexity – Why does doubling the speed give this improvement?

If we can solve a problem of size $n = 10^6$ in 20 seconds, and then we double the machine speed, how big of a size problem can we now solve given a certain algorithm complexity?

The way I been solving these is doing something like:

If complexity is O($\log_2{n})$ and $m$ is the new input size that the faster machine can handle in the same amount of time:
$$ \dfrac{\log_2{}m}{\log_2{}n} = 2$$
$$ {\log_2{}m} = 2{\log_2{}n} $$
$$ {\log_2{}m} = {\log_2{}n^2} $$
$$ {m} = {n^2} $$

So the faster machine can do problem size of $[10^{6}]^{2} = 10^{12}$ in the same amount of time.

If complexity is O($n\log{} n$):

$$ \dfrac{m\log_2{}m}{n\log_2{}n} = 2 $$
$$ {m\log_2{}m} = 2({n\log_2{}n}) $$

I'm not really seeing how to solve algebraically… I don't see how I could plug in $n= 10^6$ to try to approximate m either.

How could I go about solving for m if the complexity is O($n\log{} n$)?

Best Answer

Your question is how to find, for a given "complexity" function $T$ (that is, your algorithm takes time $T(x)$ on an input of size $x$), a number $m$ such that $T(m) = 2T(n)$.

You will not always be able to find a closed-form algebraic expression for $m$.

In this particular case of $T(x) = x \log x$, there is no closed-form expression in terms of elementary functions, but there is one using the Lambert-W function which is defined as satisfying $$W(z)e^{W(z)} = z$$

If $m \log m = y$, we can write this as $e^{\log m} \log m = y$ so that $\log m = W(y)$. This gives $$m = e^{W(y)}$$ as your answer. This is also mentioned on Wikipedia.

In particular for $y = 2n \log n$, you can get the answer in terms of $m$ as $$m = e^{W(2n \log n)}$$

If the function you care about has logarithms to base $2$ or to some other base $b$, the expression in terms of $n$ is still the same: $$m \log_b m = 2n \log_b n \iff m \frac{\ln m}{\ln b} = 2n \frac{\ln n}{\ln b} \iff m \ln m = 2n \ln n$$

You can use some computer-algebra system that implements $W$. For $n = 10^6$, this gives $m \approx 1.910480 \times 10^6$. You can also use Newton's approximation with initial guess of $2n$ to get $m \approx 2n - \frac{2n \ln 2}{\ln (2n) + 1}$ which [gives](http://www.wolframalpha.com/input/?i=2n-(2n+ln2)%2F(ln(2n)%2B1%29+for+n+%3D+10%5E6) $1.91061 \times 10^6$ which is not too far from the correct value. See this question for other ways of approximating the Lambert W function.

For a general function $T$, there may not be a way to express $m$ as a function of $n$, even using well-known non-elementary functions. So there are two ways you may proceed:

  1. If you want an (approximate) analytic expression, you can use Newton iteration with a reasonable initial guess. That is, you're trying to find $m$ such that $$f(m) = T(m) - 2T(n) = 0,$$ so with some initial guess $m_0$ (I picked $m_0 = 2n$ above for the case of $T(x) = x\log x$), you get the approximation $$m_1 = m_0 - \frac{f(m_0)}{f'(m_0)} = m_0 - \frac{T(m_0) - 2T(n)}{T'(m_0)}$$

  2. If you want the actual numerical value for a particular function, you can still Newton's method (with enough iterations), or even simpler, just use binary search.

// Given an increasing function f, finds x such that f(x) = y (to within epsilon)
function binary_search(f, y, eps) {
    if (eps === undefined) eps = 1e-3;
    let lo = 0;
    let hi = y * Math.max(1e10, f(y)); // Hope this is enough
    // Invariant: f(lo) <= y < f(hi)
    while (hi - lo > eps) {
        let mid = lo + (hi - lo)/2;
        if (f(mid) <= y) lo = mid;
        else hi = mid;
    }
    return lo;
}

// Finds m for which f(m) = 2f(n)
function where_double(t, n, eps) {
    return binary_search(t, 2 * t(n), eps);
}

Try it out

Related Question