14
$\begingroup$

Context: I am learning Dijstra's Algorithm to find shortest path to any node, given the start node. Here, we can use Fibonnacci Heap as Priority Queue. Following is few lines of algorithm:

For each vertex in PriorityQueue{     do_something() } 

If $V$ is the number of vertices, the subsequent lookup times in the priority queue will be: $$O(\log V), O(\log V-1), \ldots$$

Question:

What would the value of $O(\log V) + O(\log V-1) + O(\log V-2) + .. + O(\log 1)$?

2 Answers 2

17

You want to find the sum: $$\sum_{n=1}^N{\log{n}} = \log \prod_{n=1}^N {n} = \log(N!)$$ Now, using Stirling's approximation: $$\log N! \sim N\log N$$

  • 0
    Nitpick: In the first equation, would the rightmost "log(n!)" be "log(N!)", i.e. 'N' instead of 'n'? (From the summation expression, my interpretation is that, 'n' is a variable, whereas 'N' is a constant.)2014-09-09
  • 0
    @Arun - thanks, corrected.2014-09-09
3

$$\log V+\log(V-1)+\log(V-2)+\cdots+\log2+\log1=\log(V!)\sim V\log V$$ The asymptotic $O(V\log V)$ is easy: either one remembers Stirling formula, or one note that the sum on the left is $\leqslant V\log V$ and, keeping only $\frac12V$ terms, $\geqslant\frac12V\log\left(\frac12V\right)\sim\frac12V\log V$.