Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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<x\leqslant 1}\theta(x) = -(1+\ln\ln{2})/\!\ln{2} \simeq -0.9139$ and $\min_{0<x\leqslant 1}\theta(x) = \theta(1) = -1$.

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?

share|improve this question
    
lg? What's lg?? –  Gerry Myerson Sep 21 '12 at 13:01
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. –  Christian Sep 21 '12 at 16:08
    
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? –  Erick Wong Sep 21 '12 at 16:30
    
I would like an answer in the form $n=2^p+k$, where $p$ is a positive integer and $k$ is an integer. –  Christian Sep 21 '12 at 16:54

2 Answers 2

up vote 3 down vote accepted

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$

share|improve this answer
    
Ross, you are right. I edited the text to reflect that there is no unicity. Did you hint at a deeper problem? –  Christian Sep 12 '12 at 15:33
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. –  Ross Millikan Sep 12 '12 at 15:43
    
I rephrased completely. Let me know if I get closer to a clearer question. –  Christian Sep 12 '12 at 17:09

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.

share|improve this answer
    
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. –  Christian Sep 28 '12 at 18:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.