Почему операция s += "string" в цикле иногда работает за O(1), а иногда за O(N)?

Это оптимизация реализации CPython, а не гарантия языка: при подходящих условиях буфер строки расширяется без копирования старого содержимого. Иначе создаётся новая строка с копированием O(N).

Оптимизация зависит от единоличного владения строкой, её внутреннего представления и возможности расширить память. Дополнительная ссылка на прежнюю строку или необходимость сменить представление могут потребовать копирования. Даже подходящий realloc не гарантирует постоянное время. Поэтому цикл конкатенаций нельзя считать безусловно линейным; надёжный способ собрать много частей — список и ''.join(parts), где итоговая память выделяется с учётом общей длины.

Источник: github.com.