On the Worst-Case Complexity of TimSort
drops.dagstuhl.de
On the Worst-Case Complexity of TimSort
1–10 of 78 posts
Re: On the Worst-Case Complexity of TimSort
#2Not good that Java's sort still has bugs.
Re: On the Worst-Case Complexity of TimSort
#3Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n?
Memories on the subject are not great so might be saying bullshit in here
Re: On the Worst-Case Complexity of TimSort
#4How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?
Re: On the Worst-Case Complexity of TimSort
#5Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n? Memories on the subject are not great so might be saying bullshit in here
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.
Re: On the Worst-Case Complexity of TimSort
#6How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?
It’s taking about the implementations in the respective standard libraries, which are apparently different.
Re: On the Worst-Case Complexity of TimSort
#7Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n? Memories on the subject are not great so might be saying bullshit in here
In the worst case, rho is equal to n, and you get O(n log n). However, O(n + n log rho) gives a better description of how it performs on partially sorted arrays.
Re: On the Worst-Case Complexity of TimSort
#8Given that rho can vary with the input and is completely arbitrary value, shouldn’t be also called n? Memories on the subject are not great so might be saying bullshit in here
n varies with the input as well :) But yes, since ρ is bounded by n you can reduce the complexity to O(n log n) again, but i think the important part here is to distinguish the complexity against other sorting algorithms and Timsort improves things for specific inputs as they note.
Re: On the Worst-Case Complexity of TimSort
#9How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?
[deleted]
Re: On the Worst-Case Complexity of TimSort
#10How is it that the abstract is talking about "Java version" and "Python version" when discussing computational complexity? Aren't algorithms algorithms, independent of the language you're implementing them in?
Yes. If the java have a different complexity it is a different algorithm.
To the writers defense, they have to algorithm in pseudo code in the article