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 $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?

  • $\begingroup$ The math looks correct. I wouldn't have guessed that factor of $1/n$. Additionally, numeric data for smallish $n$ ($\le 40$) bears it out. Interesting problem. $\endgroup$ – Rick Decker Dec 3 '12 at 18:21
  • $\begingroup$ Update. With the help of a CAS, I verified your estimate for $n<10000$. I found that for those $n$ the ratio of $f(n)$ and $2^n/n$ is always in the range $(1, 4)$. $\endgroup$ – Rick Decker Dec 3 '12 at 21:01
  • $\begingroup$ Excellent, I already failed to get a CAS providing numbers for high n in a reasonable amount of time. Thank you! $\endgroup$ – Simon S Dec 3 '12 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.