Maximum Execution Time of Arduino Mega2560

Depends on what the "execution" is doing.
A post from 2008 says the basic operation of toggling a pin takes about 10 microseconds, however bypassing the Arduino framework can make it 20x faster.

If you are doing things that need precise timing then you need to disable interrupts which has the unfortunate side effect of stopping millis() from working.