Kétszer olyan hosszú számok összeszorzása nem négyszer annyi ideig tart? Miért?

Mert a számnítógép algoritmusa a szorzásra nem lineárisan skálázódik. Ennek sok oka lehet, de talán a legfontosabb az, hogy a számítógép kettes számrendszerben számol, és emiatt sok műveletet máshogy is el lehet végezni, mint ahogy megszoktad. Tehát a szorzást a számítógép messze nem úgy fogja elvégezni, mint ahogy te tennéd kézzel, vagyis nem szükségképpen lesz rá igaz, hogy ha mindkét bemenetének a hosszát megduplázzuk, akkor négyszer annyi ideig tart majd.

Igen, háromszorosára nő, nem négyszeresére. Van erre egy okos algoritmus, valahol.