Какова сложность алгоритмов (Big(O)) встроенных JS методов?
1. Сложность зависит алгоритма, используемого в конкретной реализации. Потому в V8 сложность может быть совсем не такой, как в JS-движке Firefox.

2. Смотреть исходный код. Тем более, что он открыт.

Добавление к строке по одной букве - это повторение N раз конкатенации строк. Потому сложность и получается O(N**2). Никакого отношения к оценке вычислительной сложности конкатенации это пример не имеет.
В реальном мире сложность конкатенации строк длинной N и M даже в худшем случае не превосходит O(N + M).
Представление строк в разных JS движках разное.

В V8 строка может быть представлена как массив или как дерево. При конкатенации строк как раз используется дерево. Есть даже проект flatstr, который конвертирует древообразное представление в плоское, чтобы прочие операции над строкой выполнялись быстрее.