Time complexity fro Dijkstra's algorithm

Question

As I read the time complexity for Dijkstra's algorithm on the unweighted graph using queue is O(n2) in the worst case. I assume this is because od bfs and dfs. BFS processes all the vertices during the marking phase and dfs is used for tracing back. They both have linear time complexity. But I'm not sure if this logic is correct.

Also for weighted graph, I know that the time complexity is O(EVlogV),where E is edges and V vertices. I think this is because of priority queue and I understand how priority queue works but still don't understand the O notation.

Jacob Steinebronn Jacob Steinebronn · Accepted Answer · 2020-06-03T21:41:58

Dijkstra's is not necessary for an unweighted graph. You can simply do a single BFS/DFS (Whichever you prefer, they're both O(E+V) anyway).

Big-O notation denotes the "Time complexity" of an algorithm. In other words, as the parameters of the problem increase, how does the runtime of your algorithm increase? Let's look at a few examples:

int two_plus_n(int n){
    return 2+n;
}

This algorithm is O(1), since no matter what N is, the algorithm will run in a constant amount of time.

int bad_2_times_n(int n){
    int ans = 0;
    for(int i=0;i<n;i++)
        ans+=2
    return ans;
}

This algorithm is O(n), since as you increase N, the number of steps increases at a linear rate with N. Big-O notation can get complicated with more complex algorithms. I suggest if you don't fully grasp the concept, you step back from an algorithm as complex as Dijkstra's and reinforce your understanding of runtime analysis.

Time complexity fro Dijkstra's algorithm

1 Answers