I was trying to bound the maximum cost of top-down merge sort: $ f(0) = f(1) = 0,\quad f(n) = n\lceil{\lg n}\rceil - 2^{\lceil\lg n\rceil} + 1, $ where $\lg n$ is the binary logarithm of $n$ and $\lceil{x}\rceil$ is the smallest integer greater than or equal to $x$. Let $\{x\}$ be the fractional part of $x$. I made two cases:
- If $n=2^p$, then $f(n) = n\lg n - n + 1$;
- else $\lceil\lg n\rceil = \lg n -\{\lg n\}+1$ and $f(n) = n\lg n + \theta(1-\{\lg n\}) \cdot n + 1$, with $\theta(x) := x - 2^x$. The derivative of $\theta$ shows that $\max_{0
and $\min_{0 .
So we have $n\lg n - n + 1 \leqslant f(n) < n\lg n - 0.91 n + 1.$ Considering $\theta(1-\{\lg n\})$ again, the lower bound is tight if $\{\lg n\} = 0$ or, equivalently, $n=2^p$.
What I want is to characterise the $n$ for which $f(n)$ is the closest to the upper bound: $\theta'(x) = 0 \Leftrightarrow x = -\lg\ln 2$, so $\theta'(1-\{\lg n\}) = 0 \Leftrightarrow \{\lg n\} = 1 + \lg\ln 2$.
How can I characterise the natural numbers $n$ such that $\{\lg n\}$ is as close as possible to $1 + \lg\ln 2$? For instance, could it be $n=2^p-1$? $2^p+1$?
EDIT In the comments, the real solution is $2^k\ln 2$, which raises the question of the integer solution. Assuming that the nearest integer is the solution, the first values for $k=1$ to $12$ are $2$, $3$, $6$, $11$, $22$, $44$, $89$, $177$, $355$, $710$, $1420$, $2839$. Is the assumption right? What is the general term?