6

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?

Rócherz
  • 3,976
Viraj
  • 163
  • 3
    Approximately? Calculate $\int_2^{n+1} x\log x,dx$. – André Nicolas Oct 05 '15 at 19:29
  • 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. – Rory Daulton Oct 05 '15 at 19:30
  • 1
    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. – André Nicolas Oct 05 '15 at 19:37
  • @RoryDaulton I thought, point 1 says that. But if not, I will be clearer next time. – Viraj Oct 06 '15 at 20:04

2 Answers2

8

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))$.

Ben Grossmann
  • 225,327
1

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.

Claude Leibovici
  • 260,315