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$\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
    lg? What's lg??2012-09-21
  • 3
    It is the binary logarithm. I am a computer scientist and the notation $\lg n$ is often preferred to $\log_2 x$, due to its frequency.2012-09-21
  • 0
    Ross Millikan's comment suggests taking $n = 2^p \ln 2$ rounded to the nearest integer. Certainly within any given dyadic interval $[2^k,2^{k+1})$ this will be the best (if we round a bit more judiciously). Are you asking for the rare cases where this approximation is much better than average?2012-09-21
  • 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
    Ross, you are right. I edited the text to reflect that there is no unicity. Did you hint at a deeper problem?2012-09-12
  • 1
    @Christian: you have said $x=2^n \ln 2$ for some natural $n$. For a given one, you can check whether $\{(n-1) \ln 2\}$ is greater or less than $0.5$. If you look through the $n$'s, you should be able to get as close to an integer as you like. I don't really understand what you are asking.2012-09-12
  • 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