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

18

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