In this demo, we will compute some Sage runtimes and graph them.
Here are actual runtimes. You may want to repeat this if you get something weird; it could depend on what the Sage server is doing!
This one is an algorithm which does not depend on $n$:
This one is an algorithm that does a fixed task for each bit of $n$. The graph is showing runtime vs. bitlength of n.
This is an algorithm that runs a doubly-nested loop through the bits of n:
For comparison, here’s an algorithm that does a fixed task $n$ times instead of once per bit of $n$:
Let’s try the Euclidean algorithm as Sage implements it. This is interesting, since the gcd has a lot of variation depending on the factorization of $n$, and there’s probably a fixed overhead built into the runtime, etc.