New answers tagged computational-complexity
5
The prototypical graph search algorithm Dijkstra's algorithm for finding the shortest paths between nodes in a graph which works for unbounded non-negative weights has a time complexity for $O(|V|^2)$ where $|V|$ is the number of nodes/vertices in a graph which is in $P$.
There are special cases where further knowledge (such as heuristics) or the graph ...
4
You might want to read the paper DIFFERENT VERSIONS OF THE SAVINGS METHOD FOR THE TIME LIMITED VEHICLE ROUTING PROBLEM[1] which gives time complexities between $O(n^3)$ and $O(n^2\log(n))$ note that in these complexity analysis the number of nodes not nodes as $n$. The reason why it is $n^2$ and not $n$ is this part of the algorithm:
Taken from EOR 151 – ...
4
I invite you to first check Wikipedia pages on computational complexity and Big O notation. Then, I would recommend you to study the celebrated book "Introduction to Algorithms" written by Cormen, Leiserson, Rivest, and Stein. It will allow you to improve your knowledge and understanding of problem and algorithm theoretical complexity.
Top 50 recent answers are included