News for hackers. Stuff that matters.

A comment on On the Worst-Case Complexity of TimSort. Parent comment

Re:On the Worst-Case Complexity of TimSort by ygra on Friday August 31, 2018 @03:16AM (#17883567)
Here, ρ is not independent of n, though
[ Parent | on HN ]
Re:On the Worst-Case Complexity of TimSort by ehsankia on Friday August 31, 2018 @04:00AM (#17883769)
It sort of is though. You can have a really large N with rho = 1, just like you can have a really small N with rho=N. They're orthogonal variables, and they both impact the run time.
[ Parent | on HN ]
Re:On the Worst-Case Complexity of TimSort by AstralStorm on Friday August 31, 2018 @03:49AM (#17883722)
Rho is always 1 to n as defined.

In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.

[ Parent | on HN ]