4
$\begingroup$

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?

  • 0
    I would like an answer in the form $n=2^p+k$, where $p$ is a positive integer and $k$ is an integer.2012-09-21

2 Answers 2

3

I don't think your $x$ is well defined. $1+ \lg \ln 2 \approx = 0.47123$ but there are many $x$'s to choose from. Note that $2^{(1+ \lg \ln 2)}=2 \ln 2$, so $x=2 \ln 2$ is a solution with the nearest integer being $1$, but so is $x=2^{10} \ln 2\approx 709.78271289$ with the nearest integer being $710$

  • 0
    I rephrased completely. Let me know if I get closer to a clearer question.2012-09-12
1

I think Ross has answered your question, but I'll try a different way to present it. If the fractional part of $\log_2n$ is close to $1+\log_2\log 2$, that says $\log_2n$ is close to $m+\log_2\log 2$ for some integer $m$, which says $n$ is close to $2^m\log2$ for some integer $m$. I doubt there's any way to characterize those integers $m$ for which $2^m\log2$ is close to an integer.

  • 0
    Thank you for your helpful complement. Since there seems no way to find a better characterization of those integers, I accepted Ross Millikan's answer and up-voted yours.2012-09-28