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).
- Sort the numbers received until now
- 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?
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))$.