3 ms·

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

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.

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.