Thing is, you don't calculate anything while the player is navigating the world, so no more CPU power is required. The only difference is that the world/level data has been generated by mathematics rather than manually using a world editor.
For example, the Midwinter games (to use what is now rather a tired example) generated a square mile of terrain at a time. If the player navigated outside that area, there would be a 10 second pause while the CPU calculated the next square mile of terrain (when considering the delay, bear in mind that this was on an 8Mhz 68000 CPU!

)