сдаётся мне, что в любой вселенной будет второй вариант, но доказывать лень :)
Если постараться, можно придумать хитрую задачу с хитрым сценарием, где подойдёт хитрая структура данных. Например, в Lempel-Ziv строки хранятся в словаре как префиксы и ссылки на другие словарные позиции. Если у нас есть задача, где любая строка это либо один символ, либо конкатенация строк, и нам нужен словарь для строк, то стоимость конкатенации будет O(1). Если хранить строки не в виде дерева, а в виде дага, то при подсчёте их длины часть подстрок будет повторяться. Если функция LEN это учитывает, и сохраняет длину уже подсчитанных подстрок, то LEN(foo) + LEN(bar) может выполняться дольше, чем LEN(foo + bar). Но это я так, чисто гипотетически, чтобы от работы отвлечься. На практике, конечно, не знаю задачи, где такое бы могло потребоваться.