Dijkstra Algorithm Time Complexity

Question

I am new to Dijkstra Algorithm.

My question is that: for an undirected graph G with n nodes and m edges, the time complexity for Dijkstra Algorithm to find shortestst path is o((n+m)logn). However, if the G is connected, why this time complexity can be also expressed as o(mlogn)?

Cheers

You've used little-o, but do you mean big theta?

Paul Hankin
– Paul Hankin

2021-04-18 07:48:13 +00:00
Commented Apr 18, 2021 at 7:48 — Paul Hankin
– Paul Hankin, Commented Apr 18, 2021 at 7:48

ntg · Accepted Answer · 2021-04-18 18:10:38Z

1

If it is not connected, say in the case where there is only one edge (m=1), then it can be it is o(nlgn). That is why in the general case it is o((m+n)lgn).

If it is connected, there should be a tree that connects the whole graph (length n-1), so m is at least n-1: (m>=n-1). So for purposes of small O notation (Small O:f is dominated by g asymptotically), I can replace n by m: o((m+1+m)lgn) "=" o(mlgn)

edited Apr 18, 2021 at 18:10

answered Apr 18, 2021 at 6:33

ntg

14.4k10 gold badges85 silver badges107 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Dijkstra Algorithm Time Complexity

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related