I/O Complexity vs Space Complexity vs Time Complexity

Question

I am struggling about the terminology between I/O complexity vs Space Complexity vs Time Complexity.

I know what time complexity is. But, are I/O complexity and space complexity same thing?

Thank you for the answers in advance.

Answer 1

My understanding is as follows:

1. time complexity represents operations (runtime) growth
2. space complexity represents memory usage growth
3. I/O complexity represents I/O operations (runtime) growth

Yes the time and I/O are similar. The difference is ALU instructions are much much more faster then I/O these days (that was not true on old architectures and I/O complexity was ignored). So it is not the same if you are computing something at once or divide it into sub-chunks with the need to store/restrore sub-results with I/O. The time complexity is the same but the I/O complexity is not and greatly affect runtime if not carefull.

For example common mistake from OpenGL is to load texture into GPU every frame instead of only once. It can be considered as I/O operation even if it is memory transfer (usually using DMA). The rendering time complexity is the same ... but I/O is not and the fps can drop significantly. In case you got a lot of textures you load them on demand (not per frame but for example per level, building, part of map etc ...) so fps will still be high but at cost of the load times between games/level/... Same principle applies to any I/O related stuff not just graphics ...