On the Worst-Case Complexity of TimSort

Re:On the Worst-Case Complexity of TimSort by phoe-krk on Friday August 31, 2018 @03:14AM (#17883555)

It shouldn't be called n because then `n log n` and `n log m` convey different meanings. In the first case, `n` is one and the same variable, where in the second, `n` and `m` are independent of each other.

You can call it `m` or `rho` or whatever, just use a different variable.

[ Parent | on HN ]

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 ]