Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

New answers tagged


Algorithms don't care whether you find out what edges lead from a vertex by looking them up in an array, by calling a function called get() or by waiting for divine revelation. The only problem with Dijkstra's algorithm is that, as it is usually described, it starts by setting the distance estimate of every node to infinity and adding every node to a queue. ...


Obviously you can't say it's $O(N^3)$ because X might grow a lot faster than N. But you can't even say it's O (N x M x X), because you don't know how often the "list.append(count)" is executed and what the time complexity of that operation is.


As you have mentioned that $ N, M, X $ are variables, the time complexity would be $ O(N*M*X) $. A possible counter argument for the complexity not equal to $ O(N^3) $ is, what if the rate of increase of $ X $ is greater than rate of increase of $ N $ ?

Top 50 recent answers are included