How to calculate n log n = c

问题:

I have a homework problem for my algorithms class asking me to calculate the maximum size of a problem that can be solved in a given number of operations using an O(n log n) algorithm (ie: n log n = c). I was able to get an answer by approximating, but is there a clean way to get an exact answer?

回答1:

There is no closed-form formula for this equation. Basically, you can transform the equation:

 n log n = c
log(n^n) = c
     n^n = exp(c)

Then, this equation has a solution of the form:

n = exp(W(c))

where W is Lambert W function (see especially "Example 2"). It was proved that W cannot be expressed using elementary operations.

However, f(n)=n*log(n) is a monotonic function. You can simply use bisection (here in python):

import math

def nlogn(c):
    lower = 0.0
    upper = 10e10
    while True:
        middle = (lower+upper)/2
        if lower == middle or middle == upper:
            return middle
        if middle*math.log(middle, 2) > c:
            upper = middle
        else:
            lower = middle

回答2:

the O notation only gives you the biggest term in the equation. Ie the performance of your O(n log n ) algorithm could actually be better represented by c = (n log n) + n + 53.

This means that without knowing the exact nature of the performance of your algorithm you wouldn't be able to calculate the exact number of operations required to process an given amount of data.

But it is possible to calculate that the maximum number of operations required to process a data set of size n is more than a certain number, or conversely that the biggest problem set that can be solved, using that algorithm and that number of operations, is smaller than a certain number.

The O notation is useful for comparing 2 algorithms, ie an O(n^2) algorithm is faster than a O(n^3) algorithm etc.

see Wikipedia for more info.

some help with logs