4 ms·

This reads like a criticism of complexity analysis, but really you're just describing it. By definition and by design, algorithmic complexity analysis only show

This reads like a criticism of complexity analysis, but really you're just describing it. By definition and by design, algorithmic complexity analysis only shows you how an algorithm behaves asymptotically. That means it's often not the right tool for selecting an algorithm with optimal real-world performance, but I think that's less a fault of the tool than it is a fault of the tool selector. Saying, "complexity analysis ignores constant factors and small-data size performance" is sort of like saying "hammers ignore the threading on screws".

Retric 5y ago
Saying something is a poor fit in the real world is a perfectly valid criticism. Arguably complexity analysis is such a poor fit programmers should never actually use it, but vastly simplifying problems can make for a good first approximation.
- alex_smart 5y ago
  Saying "why do we teach programmers complexity analysis in a word RAM model, there are no idealized RAM machines that behave like that in the real world" is no better than saying "why do we teach people Euclidean geometry, there are no such idealized geometrical systems in the real world". The point is that: 1. The analysis is useful and instructive. 2. It teaches you how to analyse computing models, starting from a simple one, so that when you need to, you can build and analyse more complex models specific to your domain.
  - Retric 5y ago
    In the real world spacetime is very close to Euclidean geometry near earth. Complexity analysis on the other hand can be wrong by literal orders of magnitude. If carpenters needed to worry about the internal angles of a triangle a ding up to between 9,672 and 1.72 degrees then I think people would consider Euclidean geometry a waste of time, but 180 +/- 0.0000001 is fine.
    - alex_smart 5y ago
      You are responding to an argument I never made. You don't teach children Euclidean because they would actually ever need to calculate the area of a triangle. You teach them geometry because it is a good exercise in working with logic, proofs and mathematical models. >Complexity analysis on the other hand can be wrong by literal orders of magnitude. Seeing how complexity analysis only applies to the asymptotic behavior of an algorithm, I don't even know how to make any semantic sense of that statement. It is not even wrong.
      - Retric 5y ago
        > only applies to asymptotic behavior. This is false, complex analysis is vastly more than just Big O, other resources like memory usage are also considered as are exact results.
        alex_smart 5y ago
        Can you explain what it means for a complexity analysis result to be wrong by literal orders of magnitude? I don't understand what that means, even with the clarification.
        Retric 5y ago
        Memory usage is perhaps the easiest to understand. Allocation and deallocation to specific addresses can result in a lot of unusable address space depending on the hardware and OS. There is actually a huge body of work around memory allocation due to such issues. Ex: Suppose you are allocating memory for a growing array. It’s allocated (+) and deallocated (-) in sequence. So +1000, then +1001, -1000, creating a (1000 wide gap at the start) but your next +1002 doesn’t fit in the gap. you now have 1001 bytes of allocated but due to fragmentation in effect 2001 are used up. This one isn’t that bad the second time around you you have a 2001 byte wide free space, but in more complex situations you can run out of memory vastly sooner than expected. On PC’s virtual memory mapping generally means you don’t need to worry about this, but it used to be a huge pain and it can still be an issue for embedded systems. PS: Not that this is 100% solved on PC’s, it’s still possible to run out of physical RAM much sooner than expected just significantly less likely.
- ravi-delia 5y ago
  I think you and the person you responded to are talking past each other a little bit. Complexity analysis may well be a poor fit, but still not as poor as a hammer's screw-turning ability. Complexity's poor fit to the real world is a criticism of its use as a programmer's tool, not the concept itself.
- munificent 5y ago
  > Arguably complexity analysis is such a poor fit programmers should never actually use it I've never once felt that way in my career. I've often found that the insight I get from an algorithm's complexity is not a complete picture of its worthiness for a particular problem, but it is almost always a necessary piece of the puzzle. I would never feel confident using an algorithm that I'd only empirically measured on some number of hand-chosen datasets because then who knows how it will behave when a user throws something unexpected at it.

Retric 5y ago

Saying something is a poor fit in the real world is a perfectly valid criticism. Arguably complexity analysis is such a poor fit programmers should never actually use it, but vastly simplifying problems can make for a good first approximation.

alex_smart 5y ago
Saying "why do we teach programmers complexity analysis in a word RAM model, there are no idealized RAM machines that behave like that in the real world" is no better than saying "why do we teach people Euclidean geometry, there are no such idealized geometrical systems in the real world". The point is that: 1. The analysis is useful and instructive. 2. It teaches you how to analyse computing models, starting from a simple one, so that when you need to, you can build and analyse more complex models specific to your domain.
- Retric 5y ago
  In the real world spacetime is very close to Euclidean geometry near earth. Complexity analysis on the other hand can be wrong by literal orders of magnitude. If carpenters needed to worry about the internal angles of a triangle a ding up to between 9,672 and 1.72 degrees then I think people would consider Euclidean geometry a waste of time, but 180 +/- 0.0000001 is fine.
  - alex_smart 5y ago
    You are responding to an argument I never made. You don't teach children Euclidean because they would actually ever need to calculate the area of a triangle. You teach them geometry because it is a good exercise in working with logic, proofs and mathematical models. >Complexity analysis on the other hand can be wrong by literal orders of magnitude. Seeing how complexity analysis only applies to the asymptotic behavior of an algorithm, I don't even know how to make any semantic sense of that statement. It is not even wrong.
    - Retric 5y ago
      > only applies to asymptotic behavior. This is false, complex analysis is vastly more than just Big O, other resources like memory usage are also considered as are exact results.
      - alex_smart 5y ago
        Can you explain what it means for a complexity analysis result to be wrong by literal orders of magnitude? I don't understand what that means, even with the clarification.
        Retric 5y ago
        Memory usage is perhaps the easiest to understand. Allocation and deallocation to specific addresses can result in a lot of unusable address space depending on the hardware and OS. There is actually a huge body of work around memory allocation due to such issues. Ex: Suppose you are allocating memory for a growing array. It’s allocated (+) and deallocated (-) in sequence. So +1000, then +1001, -1000, creating a (1000 wide gap at the start) but your next +1002 doesn’t fit in the gap. you now have 1001 bytes of allocated but due to fragmentation in effect 2001 are used up. This one isn’t that bad the second time around you you have a 2001 byte wide free space, but in more complex situations you can run out of memory vastly sooner than expected. On PC’s virtual memory mapping generally means you don’t need to worry about this, but it used to be a huge pain and it can still be an issue for embedded systems. PS: Not that this is 100% solved on PC’s, it’s still possible to run out of physical RAM much sooner than expected just significantly less likely.
ravi-delia 5y ago
I think you and the person you responded to are talking past each other a little bit. Complexity analysis may well be a poor fit, but still not as poor as a hammer's screw-turning ability. Complexity's poor fit to the real world is a criticism of its use as a programmer's tool, not the concept itself.
munificent 5y ago
> Arguably complexity analysis is such a poor fit programmers should never actually use it I've never once felt that way in my career. I've often found that the insight I get from an algorithm's complexity is not a complete picture of its worthiness for a particular problem, but it is almost always a necessary piece of the puzzle. I would never feel confident using an algorithm that I'd only empirically measured on some number of hand-chosen datasets because then who knows how it will behave when a user throws something unexpected at it.