3
$\begingroup$

I am working on an algorithm to calculate the median of the current input stream of numbers. I am using the following method (I know it is not the best but I need to calculate its complexity).

  1. Sort the numbers received until now
  2. Return the middle element.

Sorting takes $n\log n$ time so the complexity for this approach is $$1\log1 +2\log2 +3\log3 +\ldots +n\log n,$$ where $n$ is the number of input elements.

How do I calculate the sum of such a series?

$\endgroup$
  • 3
    $\begingroup$ Approximately? Calculate $\int_2^{n+1} x\log x\,dx$. $\endgroup$ – André Nicolas Oct 5 '15 at 19:29
  • $\begingroup$ You do not explicitly say so, but are we to assume that you resort the list of numbers received every time you receive another number? Welcome to this site, but please make sure your question is well-defined. $\endgroup$ – Rory Daulton Oct 5 '15 at 19:30
  • 1
    $\begingroup$ That's good too. But when we are evaluating the performance of a procedure, an estimate that is a bit too big is better than an estimate that is a bit too small. $\endgroup$ – André Nicolas Oct 5 '15 at 19:37
  • $\begingroup$ @RoryDaulton I thought, point 1 says that. But if not, I will be clearer next time. $\endgroup$ – Viraj Oct 6 '15 at 20:04
6
$\begingroup$

The sum of this series is an approximation of (and is approximated by) the integral $$ \int_1^{n+1} x\log(x)\,dx = \Theta(n^2\log(n)) $$ So, your sum of logs will be $\Theta(n^2\log(n))$.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If the $i$'s are consecutive integer numbers, $$\sum_{i=1}^m i \log(i)=\log (H(m))$$ where $H(m)$ is the hyperfactorial function.

For large values of $m$, Stirling type expansions give $$H(m)=m^2 \left(\frac{1}{2} \log \left({m}\right)-\frac{1}{4}\right)+\frac{1}{2} m \log \left({m}\right)+\left(\log (A)+\frac{1}{12} \log \left({m}\right)\right)+\frac{1}{720 m^2}+O\left(\frac{1}{m^4}\right)$$ where $A$ is Glaisher constant.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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