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)$?
$\endgroup$2 Answers
$\begingroup$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$$
$\endgroup$ 0 $\begingroup$$$\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$.
$\endgroup$
