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

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

If we can solve a problem of size n=106n = 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(log2n)\log_2{n}) and mm is the new input size that the faster machine can handle in the same amount of time:
log2mlog2n=2 \dfrac{\log_2{}m}{\log_2{}n} = 2
log2m=2log2n {\log_2{}m} = 2{\log_2{}n}
log2m=log2n2 {\log_2{}m} = {\log_2{}n^2}
m=n2 {m} = {n^2}

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

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

mlog2mnlog2n=2 \dfrac{m\log_2{}m}{n\log_2{}n} = 2
mlog2m=2(nlog2n) {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=106n= 10^6 to try to approximate m either.

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



1 Answer


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

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

In this particular case of T(x)=xlogxT(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)eW(z)=zW(z)e^{W(z)} = z

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

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

If the function you care about has logarithms to base 22 or to some other base bb, the expression in terms of nn is still the same:
mlogbm=2nlogbn⟺mlnmlnb=2nlnnlnb⟺mlnm=2nlnnm \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 WW. For n=106n = 10^6, this gives m≈1.910480×106m \approx 1.910480 \times 10^6. You can also use Newton’s approximation with initial guess of 2n2n to get m≈2n−2nln2ln(2n)+1m \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×1061.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 TT, there may not be a way to express mm as a function of nn, even using well-known non-elementary functions. So there are two ways you may proceed:

If you want an (approximate) analytic expression, you can use Newton iteration with a reasonable initial guess. That is, you’re trying to find mm such that
f(m)=T(m)−2T(n)=0,f(m) = T(m) – 2T(n) = 0,
so with some initial guess m0m_0 (I picked m0=2nm_0 = 2n above for the case of T(x)=xlogxT(x) = x\log x), you get the approximation
m1=m0−f(m0)f′(m0)=m0−T(m0)−2T(n)T′(m0)m_1 = m_0 – \frac{f(m_0)}{f'(m_0)} = m_0 – \frac{T(m_0) – 2T(n)}{T'(m_0)}
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