Content deleted Content added
m Maintain {{WPBS}}: 2 WikiProject templates. Remove 1 deprecated parameter: field. Tag: |
JustinBlank (talk | contribs) Questioning the linear time claim |
||
Line 227:
Hello! This is a note to let the editors of this article know that [[:File:MAZE 30x20 Prim.ogv]] will be appearing as [[Wikipedia:picture of the day|picture of the day]] on June 12, 2015. You can view and edit the POTD blurb at [[Template:POTD/2015-06-12]]. If this article needs any attention or maintenance, it would be preferable if that could be done before its appearance on the [[Main Page]]. Thanks! — [[User:Crisco 1492|Chris Woodrich]] ([[User talk:Crisco 1492|talk]]) 23:50, 22 May 2015 (UTC)
{{POTD/2015-06-12}}
== Linear Time For Dense Graphs ==
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
— 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)
| |||