3 ms·

But ultimately the same problems affect both algorithms in the same way. So the best case algorithm will be slower in the real world, but should still be faster

But ultimately the same problems affect both algorithms in the same way. So the best case algorithm will be slower in the real world, but should still be faster than the other cases.

reaperducer 7y ago
Only if all algorithms are affected the same way by the same external factors, which simply doesn't happen. It's like when a Toyota and a Freightliner crash into the same wall. They both crashed at the same speed, why is one damaged more than the other?
- ntsplnkv2 7y ago
  You can come up with endless scenarios to justify it, but the fact is you can't design something that will deal with all of them. So you design for the typical scenario. Maybe there is an algorithm that boards a plane faster when there are 2 handicapped people, 3 drunks, and 1 person being late. But how typical is that? And is it realistic to design the whole algorithm around that? I would argue it isn't.
  - cgriswald 7y ago
    Real flights have those things in some numbers and a model probably ought to attempt to account for them, since, as you noted in a separate post I can’t seem to find now, they’ll affect the model negatively. The goal isn’t to find the best number of late people and wheelchairs. It’s to be able to board real flights as quickly as possible and every real flight I’ve ever seen, except the flight I took shortly after 9/11, has had some number of strollers, wheelchairs, or what have you.
s1artibartfast 7y ago
I don't think we can make that claim. There is no reason to believe the problems will affect both algorithms the same way. Some may be more fragile or failure resistant to different failure modes.
- deleted 7y ago
  [deleted]
tedunangst 7y ago
Except this is not true. Quicksort is typically faster than mergesort, but worst case it can be very much slower. The worst case does not affect both algorithms the same way.
- ntsplnkv2 7y ago
  But we are not talking about quicksort or mergesort, either way it helps prove my point. Typically faster is an interesting way of describing something. What is typical? 80% of the time?
  - tedunangst 7y ago
    Your point is that all algorithms respond the same way to inputs, and a counterexample helps prove it?
    - ntsplnkv2 7y ago
      That wasn't my point - we are talking about a specific scenario here, not "all"
      - cgriswald 7y ago
        An algorithm sees its best time complexity over some percentage of the input space. Over some other percentage it sees its worst time complexity. And, on average over the entire input space, it sees its average time complexity. The algorithms are necessarily different in what those best, average and worst are, and importantly, over what parts of the input space those categories apply. If they weren't, we'd call the algorithms mathematically equivalent and it wouldn't matter which one you chose. And if they all handled 'problem' data equally, we'd see that they all have the same performance penalty between best and average and average and worst. They don't. Sometimes best and average are equal. Sometimes worst and average are equal. Sometimes all three are equal. If your data is truly random, you should pick the algorithm with the best average time complexity. Is your data random? Almost certainly not. It might be 'random enough', or it might not be. A real world data set may fall completely within the best case of algorithm A and the worst case of algorithm B, even if the average case of B is better than the average case of A. In this case, the data points that are most likely to negatively affect an algorithm are specifically being excluded from the model. Far from comparing even the average case, we're comparing best cases. We aren't using a 'real world' data set. So it's an interesting simulation, but it isn't enough to reach any conclusions at all.

But ultimately the same problems affect both algorithms in the same way. So the best case algorithm will be slower in the real world, but should still be faster than the other cases.

reaperducer 7y ago

Only if all algorithms are affected the same way by the same external factors, which simply doesn't happen. It's like when a Toyota and a Freightliner crash into the same wall. They both crashed at the same speed, why is one damaged more than the other?

ntsplnkv2 7y ago
You can come up with endless scenarios to justify it, but the fact is you can't design something that will deal with all of them. So you design for the typical scenario. Maybe there is an algorithm that boards a plane faster when there are 2 handicapped people, 3 drunks, and 1 person being late. But how typical is that? And is it realistic to design the whole algorithm around that? I would argue it isn't.
- cgriswald 7y ago
  Real flights have those things in some numbers and a model probably ought to attempt to account for them, since, as you noted in a separate post I can’t seem to find now, they’ll affect the model negatively. The goal isn’t to find the best number of late people and wheelchairs. It’s to be able to board real flights as quickly as possible and every real flight I’ve ever seen, except the flight I took shortly after 9/11, has had some number of strollers, wheelchairs, or what have you.

s1artibartfast 7y ago

I don't think we can make that claim. There is no reason to believe the problems will affect both algorithms the same way. Some may be more fragile or failure resistant to different failure modes.

deleted 7y ago
[deleted]

tedunangst 7y ago

Except this is not true. Quicksort is typically faster than mergesort, but worst case it can be very much slower. The worst case does not affect both algorithms the same way.

ntsplnkv2 7y ago
But we are not talking about quicksort or mergesort, either way it helps prove my point. Typically faster is an interesting way of describing something. What is typical? 80% of the time?
- tedunangst 7y ago
  Your point is that all algorithms respond the same way to inputs, and a counterexample helps prove it?
  - ntsplnkv2 7y ago
    That wasn't my point - we are talking about a specific scenario here, not "all"
    - cgriswald 7y ago
      An algorithm sees its best time complexity over some percentage of the input space. Over some other percentage it sees its worst time complexity. And, on average over the entire input space, it sees its average time complexity. The algorithms are necessarily different in what those best, average and worst are, and importantly, over what parts of the input space those categories apply. If they weren't, we'd call the algorithms mathematically equivalent and it wouldn't matter which one you chose. And if they all handled 'problem' data equally, we'd see that they all have the same performance penalty between best and average and average and worst. They don't. Sometimes best and average are equal. Sometimes worst and average are equal. Sometimes all three are equal. If your data is truly random, you should pick the algorithm with the best average time complexity. Is your data random? Almost certainly not. It might be 'random enough', or it might not be. A real world data set may fall completely within the best case of algorithm A and the worst case of algorithm B, even if the average case of B is better than the average case of A. In this case, the data points that are most likely to negatively affect an algorithm are specifically being excluded from the model. Far from comparing even the average case, we're comparing best cases. We aren't using a 'real world' data set. So it's an interesting simulation, but it isn't enough to reach any conclusions at all.