Content deleted Content added
JustinBlank (talk | contribs) Questioning the linear time claim |
m Reverted edit by 137.132.215.131 (talk) to last version by JustinBlank |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 231:
The article currently claims "However, for graphs that are sufficiently dense, Prim's algorithm can be made to run in linear time, meeting or improving the time bounds for other algorithms.[10]". The reference is to Tarjan, "Data Structures and Network Algorithms", page 77. While I am only now learning about Prim's algorithm, I do not believe this is accurate. The page states:
: The running time of this implementation is dominated by the heap operations, of which there are n — 1 deletemin operations, n — 1 insert operations, and at most m — n + 1 siftup operations. By the analysis of §3.2, the total running time is 0(n d logd n + m logd n).
I cannot find anything on that page that indicates that the algorithm is ever linear. [[User:JustinBlank|JustinBlank]] ([[User talk:JustinBlank|talk]]) 19:06, 27 October 2024 (UTC)
| |||