I am wondering if there is any good upper bound other than the trivial one for $\lfloor n\log_2 n\rfloor$ (or $\lfloor \frac{n\log_2 n}{2}\rfloor$, I am not sure which one is easier to bound) for all integers $3\le n\le 2^k-1$ (or for all $2^{k-1}<n\le 2^k-1$), where $k\ge 3$ is a positive integer (or just for all large positive integers $k$).

$\lfloor x\rfloor$ means the largest integer at most $x$. Notice the base of logarithm is of 2.

I am trying to check if $$(2^k-n)(k\cdot 2^{k-1}-1)<(2^k-2)(k\cdot 2^{k-1}-1-\lfloor \frac{n\log_2 n}{2}\rfloor)$$ holds for all integers $2^{k-1}<n\le 2^{k}-1$ and $k\ge 4$, say. Therefore a good bound of $\lfloor \frac{n\log_2 n}{2}\rfloor$ other than the trivial one is needed.

  • 1
    $\begingroup$ What constitutes "good"? What's wrong with $n\log n$ as an upper bound? $\endgroup$ – Gerry Myerson Feb 14 '18 at 6:00
  • $\begingroup$ I just revised it. $\endgroup$ – Connor Feb 14 '18 at 6:08
  • $\begingroup$ How is this anyway related to combinatorics $\endgroup$ – Darkrai Feb 14 '18 at 10:33
  • $\begingroup$ @Manthanein it can be viewed as counting problem in some sense. $\endgroup$ – Connor Feb 14 '18 at 13:50

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.