Shouldn't the time complexity of Dijkstra's algorithm and Bellman Ford algorithm be O(|V|^2) and O(|V|^3) respectively? I have been reading both their pseudo code from here and here.
Both Bellman Ford algorithm and Dijkstra's algorithm look quite alike except for Bellman Ford algorithm doing the same process as Dijkstra's algorithm for |V| times (where |V| is the number of nodes). So why did every article I visit on this topic says that Dijkstra's algorithm runs in O(|v|^2) and Bellman Ford algorithm runs at O(|V||E|) time complexity? Where did I go wrong (if I really did)?
Update:
Don't you think:
|E| = (|V|^2 - |V|)/ 2 if each node is connected to each other node? So let's assume every node to be connected with every other node. Now we get, O(|V|^3) for Bellman Ford Algorithm. Am I right?
So we have O(|V||E|) = O(|V|(|V|^2 - |V|)/2) = O(|V|^3). Is that right? If not, where did I go wrong?
Shouldn't the time complexity of Dijkstra's algorithm and Bellman Ford algorithm be O(|V|^2) and O(|V|^3) respectively?
Yes(1), but that won't be a tight bound. Similarly, you could say it is O(|V|^5), and it will also be correct (recall that big O is asymptotic upper bound, not a tight one).
Many graphs are not dense, but sparse, and the number of edges connected to each vertex is sub-linear. So, if we use the |E| notation as well, we can get a better more tight (and more informative) bound.
Similarly, think of an algorithm that traverses a matrix of size nxm. It is more informative to say the algorithm is O(n*m), rather than saying it's O(max{n,m}^2), isn't it?
Regarding implementation of Dijkstra's-Algorithm, the actual complexity depends a lot on the modify value in the min heap implementation, while there are implementations that can do it in logarithmic time (giving total of O(|E|+|V|log|V|) time, some implementations don't bother and just go for the simpler solution that runs in O(|V|^2).
(1) Assuming simple graphs here