Not even large inputs. More like medium or even the larger end of small. A quadratic-time solution can often start to be noticably slow with just a few thousand

Not even large inputs. More like medium or even the larger end of small. A quadratic-time solution can often start to be noticably slow with just a few thousand items. A realistic dataset for the problem they descibed could easily be tens of millions of records even if you're not a Google-sized site.