Как вам сказали в комментариях, стандарты не предъявляют никаких требований относительно сложности времени или пространства. И что касается вашего дополнительного неявного вопроса, да, компилятор может изменить ваш код O (n log n) для запуска за O (n²) времени. Или в O (n!), Если захочет.
Основное объяснение состоит в том, что стандарт определяет правильные программы, и программа является правильной независимо от того, сколько времени требуется для выполнения или сколько памяти она использует. Эти детали оставлены для реализации.
Конкретные реализации могут компилировать ваш код любым подходящим способом. Например, было бы вполне допустимо, чтобы реализация добавляла пятисекундную задержку между каждой строкой кода, которую вы написали - программа по-прежнему корректна. Было бы также допустимо, чтобы компилятор нашел лучший способ сделать то, что вы написали, и переписать всю программу, если наблюдаемое поведение одинаково.
Однако тот факт, что реализация соответствует , не означает, что она идеальна. Добавление пятисекундных задержек не повлияет на соответствие реализации, но никто не захочет использовать эту реализацию. Компиляторы не делают этого, потому что в конечном итоге они являются инструментами, и поэтому их авторы ожидают, что они будут полезны для тех, кто их использует, а намеренно ухудшать ваш код бесполезно.
TL; DR: плохая производительность (сложность времени, сложность памяти и т. Д.) Не влияет на соответствие, но заставит вас искать новый компилятор.