# Value of Summation of log(i)

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

Question: So, what would the value of O(log V) + O(log V-1) + O(log V-2) + .. + O(log 1)?

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