Bad Qubits — Learn Quantum by Doing

Multiple choice

How do the asymptotic running times of Shor's algorithm and the classical General Number Field Sieve (GNFS) compare when factoring an n-bit number N?

Both are fully exponential in n, about 2^n, with the same leading exponent
Shor is polynomial in n, about O(n^3), while GNFS is sub-exponential in n - an exponential speedup
Shor is sub-exponential and GNFS is polynomial, so GNFS is asymptotically faster
Both are polynomial in n, but Shor has a smaller constant factor