11–20 of 78 posts
Given 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.
Given 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.
In some other typical cases (otherwise sorted array with one element inserted, two sorted arrays appended to each other) rho is 3 and 2, so also O(n).
How 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?
> In fact, there are two slightly different versions of TimSort that are currently implemented in Python and in Java respectively.
Earlier quoted context omitted.
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.
Here, ρ is not independent of n, though
How 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
It doesn't seem wrong to me to talk about different versions of the same algoritm when there are only minor differences.
Earlier quoted context omitted.
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.
Here, ρ is not independent of n, though
In randomized input with uniform statistics, should be on average (n - log n) which also gives a handle on theta notation complexity.
Given 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.
Given 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.