Content deleted Content added
Citation bot (talk | contribs) Alter: template type. | Use this bot. Report bugs. | #UCB_CommandLine 74/9214 |
Citation bot (talk | contribs) Misc citation tidying. | Use this bot. Report bugs. | #UCB_CommandLine |
||
Line 184:
where {{math|''s''<sub>2</sub>(''n'')}} is the [[Hamming weight|sum of all digits of the binary representation]] of {{mvar|n}} and {{math|''e''<sub>2</sub>(''n'')}} is the exponent of {{math|2}} in the prime factorization of {{mvar|n}}.
The average case is more complex to analyze, but it can be shown to asymptotically approach {{math|1.8814 ''n'' − 2 log<sub>2</sub>''n'' + ''O''(1)}} comparisons.<ref>{{cite journal |title=An Average Case Analysis of Floyd's Algorithm to Construct Heaps |first=Ernst E. |last=Doberkat |journal=Information and Control |volume=6 |issue=2 |pages=114–131 |date=May 1984 |doi=10.1016/S0019-9958(84)80053-4 |url=https://core.ac.uk/download/pdf/82135122.pdf |doi-access=free}}</ref><ref>{{cite
|title=Elementary Average Case Analysis of Floyd's Algorithm to Construct Heaps
|first=Tomi |last=Pasanen
| |||