2
$\begingroup$

Having $f(n) = \sum_{k=0}^n g_n(k), \; g_n(x) = \min(2^x, 2^{2^{n-x}})$ I want to know whether $\mathcal O(f(n)) \subsetneq \mathcal O(2^n)$. Since $g_n(x) \le 2^x$ it is at least $f(n) \in \mathcal O(2^{n+1}-1) = \mathcal O(2^n)$.

Graph of <span class=g_10(x)">

Let $x_n$ be the maximum point of $g_n(x)$, which is where $2^x = 2^{2^{n-x}}$. We get $f(n) = \sum_{k=0}^{\lfloor x_n \rfloor} 2^k + \sum_{k=0}^{n - \lfloor x_n \rfloor} 2^{2^k}$

Since $x_n$ solves $x + \log_2(x) = n$ we get for the second sum $\sum_{k=0}^{n - \lfloor x_n \rfloor} 2^{2^k} = \sum_{k=0}^{ \lfloor \log_2(x_n) \rfloor} 2^{2^k} \le \sum_{k=0}^{ \lfloor x_n \rfloor} 2^k$

Therefore $f(n) \in \mathcal O \big( \sum_{k=0}^{\lfloor x_n \rfloor} 2^k\big) = \mathcal O \big(2^{\lfloor x_n \rfloor} \big)$.

I'm quite unsure about the following lines, especially since this is the first time I've come across the Lambert-W-function, which is needed to solve $x + \log_2(x) = n$ (according to WolframAlpha): $x_n = {W(2^n \log(2)) \over\log(2)}$

From this paper, section 2.8, I've got $ W(x) \in \mathcal O \Bigg(\log(x)-\log(\log(x))+{\log(\log(x)) \over \log(x)}\Bigg)$

And plugging everything together (omitting constants):

$ f(n) \in \mathcal O\big(2^{ W(2^n)}\big) = \mathcal O\Bigg(2^{ \log(2^n)-\log(\log(2^n))+{\log(\log(2^n)) \over \log(2^n)}}\Bigg) = \mathcal O\Big(2^n \cdot 2^{-\log(n)}\cdot \sqrt[n]{2^{\log(n)}}\Big) = \mathcal O\Big(2^n \cdot {1 \over n} \cdot 1\Big) = \mathcal O\Big({2^n \over n}\Big)$

Is this correct? Is there some easy way to do it without Lambert-W?

  • 0
    Excellent, I already failed to get a CAS providing numbers for high$n$in a reasonable amount of time. Thank you!2012-12-03

0 Answers 0