4 ms·

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

• phoe-krk 8y ago
  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.
  • ygra 8y ago
    Here, ρ is not independent of n, though
    • deleted 8y ago
      [deleted]
    • AstralStorm 8y ago
      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.
    • ehsankia 8y ago
      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.
• matharmin 8y ago
  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.
  • pmiller2 8y ago
    Nitpick: \rho = n/2 in the worst case, if n > 1, but that still gives you O(n log n).
    • Fri31Aug 8y ago
      Why n/2? If the array is, for example, sorted in the reverse order, then there is no monotonous run at all, in which case I believe the algorithm considers each element from the array being a run in itself, giving n runs.
      • pxndx 8y ago
        Runs can be increasing or decreasing, a reversed array is a single run. Worst case is n/2 because you can always split the array in pairs (if it alternates a high and a low value for example).
        • Fri31Aug 8y ago
          Ah I didn't know it also exploited reversed runs. Amazing.
  • pelario 8y ago
    Exactly. Sometimes those are called "adaptive algorithms", in the sense that the complexity depends on some properties of the input, so even though the worst case complexity is still O(n log n), for many outputs it will do much better.
  • Scarblac 8y ago
    And in the best case (already sorted array), it's equal to 1 and the algorithm performs as O(n), which is nice to prove in one go. 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).
    • dmurray 8y ago
• ygra 8y ago
  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.