If the function was implemented as an infinite loop, would you consider the code working correctly as well? After all, the result after execution of the function is always correct (ex falso quodlibet).
Here the algorithm is quadratic but will, theoretically, always complete. Thus there is no bug, but a performance problem. I think that a bug is a mistake in a programme that causes erroneous behaviour.
Say if I was writing a programme which needed to make a computation which is doable only with a quadratic algorithm. Should I not write that programme at all because it'd be a bug, albeit in most cases it'd do the processing I needed?
I'd rather call this a mistake as long as the output from the function is as expected. I'm not saying that it's a negligible mistake to use a quadratic algo where there is a linear one though. Just that I doubt it is fundamentally a bug.
This only makes sense if you completely ignore context, which doesn't make any sense at all. The point/"bug"/mistake here is using a quadratic algorithm when it isn't necessary, not just the fact that the algorithm is quadratic. If something can be solved in O(1) time, it's a mistake to use an O(n) algorithm, and similarly, if something can be solved in O(2^(n!)) time, it's a mistake to use a O(9999^(n!)) algorithm (assuming constant factors are of similar orders of magnitude etc, as they are in the OP).