Problem: Consider a graph $G = (V, E)$ on $n$ vertices and $m > n$ edges, $u$ and $v$ are two vertices of $G$.
What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with Dijkstra's algorithm using Binary Heap ?
To clarify, Dijkstra's algorithm is run from the source and allowed to terminate when it reaches the target. Knowing that the target is a neighbor of the source, what is the time complexity of the algorithm?
Dijkstra's algorithm in this case makes $O(n)$ inserts ( $n$ if the graph is complete) and 1 extract min in the binary heap, before calculate the shortest path from $u$ to $v$.
In a binary heap insert costs $O(\log n)$ and extract min $O(\log n)$ too.
So the cost in my opinion is $O(n \cdot \log n + \log n) = O(n \log n)$
But the answer is $\Theta(n)$, so there is something wrong in my thinking.
Where is my mistake?