[解決済み] n log n = c の計算方法

質問事項

アルゴリズムの授業で、O(n log n) アルゴリズムを用いて与えられた演算回数で解くことのできる問題の最大サイズを計算せよ、という宿題があります (つまり、n log n = c) 。 私は近似することによって答えを得ることができましたが、正確な答えを得るためのきれいな方法はありますか？

解答方法を教えてください。

この方程式には閉じた形の公式はありません。基本的には、式を変形すればよい。

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

すると、この方程式は、次のような形の解を持つ。

n = exp(W(c))

ここで、Wは Lambert W関数 (特に例2参照)。このとき、次のことが証明されました。 W を初等演算で表現することはできない。

しかし f(n)=n*log(n) は単調関数です。単純にbisection(ここでは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