This reminds me of my favourite gotcha in python - that parsing integers is O(n^2). This is because (conceptually at least - there might be some optimizations

This reminds me of my favourite gotcha in python - that parsing integers is O(n^2). This is because (conceptually at least - there might be some optimizations that change the details slightly) an integer is parsed by parsing each digit in a loop, and keeping a running total `value = 10 * value + digit`. This seems O(n), until you realise that the "10 * value + digit" operation takes O(log(value)) because of the internal digit-based representation. log(value) is proportional to the number of parsed digits so far, so we can say that the `value = 10 * value + digit` step is O(n), making the whole loop O(n^2). Some basic timing tests bear this out - on my machine, a 1000-digit number takes ~10us to parse but a 1000000-digit number (which is a 1MB payload - within the possibility of maliciously provided input) takes 5sec (that is, 5000000x longer for a 1000x longer input). As a fun aside, I was able to write a replacement int() function optimised for numbers this large that is O(n log n). It does this by splitting the input string in two, parsing both sides recursively (switching to native int() below a size threshold) then joining them together with `left * 10*len(right_str) + right`. Though given that we're parsing base10 digits and the internal representation uses a power of 10 as digits (which I only learned today - I'd assumed the internal digits would be powers of 2), it would be possible to special-case parsing of base10 integers so that it's O(n), by just grouping digits directly into internal digits instead of doing true multiply operations. Given base10 parsing is by far the most common case, that's an optimization that may be worth doing.