Give an example of an n-vertex simple graph G that causes Dijkstra’s algorithm to run in Ω(n2 log n) time when its implemented with a heap

Question

Dears, I think such a graph would be dense graph.

However, why the notation is big omega? I think it should be a big o.

Justification: in a undirected dense graph, m< n(n-1); therefore, m+n< n^2;then (m+n)logn<n^2logn;then (m+n)logn = O(n^2logn)

Did the author of the book make a mistake?

It sounds like you don't understand the difference between O and Ω in this context. It is correct both to say that Dijkstra's algorithm is O(n^2 log n) and also Ω(n^2 log n) on a dense graph, but these statements have different meanings. See [this Q&A](https://stackoverflow.com/q/10376740/12299000). — kaya3, May 27 '22 at 01:26
O(f(n)) describes functions with an _upper_ bound k*f(n) for some constant k. Ω(f(n)) is same replacing _upper_ with _lower_. Here you want a graph that "forces" D's algorithm to have its _worst_ possible performance. I.e. you want to prove that f(n)=n^2 log n characterizes a _lower_ bound on its performance. I.e. the run time is Ω(n^2 log n). Since it's also O(n^2 log n), that's a tight bound. I've omitted details. — Gene, May 27 '22 at 04:15

0 Answers0