If I increase the upper number by a factor of 10, to 500000, these times become, 436 s (yes, really, 7 minutes!) and 0.20 s respectively. This suggests that the algorithm used by compgen is O(n^2) whereas the algorithm used by grep is 0(1).
I meant: grep is O(n).
