I mean, there obviously must be some compiler optimizations that enable the O(K^2) algorithm to be accepted for the worst case.

For example, I've tried binary search, given that this is a convex function, and the amount of branch prediction misses slows the thing down a lot.

I've been looking at godbolt.org output and can't figure out what is happening here.