4 ms·

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 cla

• 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.