Как изменятся асимптотические сложность и потребление памяти в задаче camelCase → snake_case, если собирать результат конкатенацией строк вместо массива символов?

При наивном копировании всей строки на каждом добавлении конкатенация даёт O(n²), а сбор частей с join — O(n). Но движки могут оптимизировать строки, поэтому фактическая стоимость зависит от реализации.

В обоих подходах итоговая строка занимает O(n). Массив частей добавляет O(n) ссылок и создаёт финальную строку при join; цепочка конкатенаций может храниться как rope и потребовать последующего выравнивания. Поэтому нельзя обещать O(n²) для любого += или меньшую память для массива без измерений на нужном движке.