String Concatenation Versus Join

Both functions build the same report string from a list of rows:

class ReportBuilder:
    def __init__(self):
        self.text = ""

    def add_line(self, line: str) -> None:
        self.text = self.text + line + "\n"

def build_report_v1(rows: list[str]) -> str:
    builder = ReportBuilder()
    for row in rows:
        builder.add_line(row)
    return builder.text

def build_report_v2(rows: list[str]) -> str:
    return "".join(row + "\n" for row in rows)

For n = len(rows), what is the total time complexity of each function, and why?

Both are O(n^2), because producing a new str inside a loop always forces a fresh copy in CPython no matter how the concatenation is written, and join is no exception.

build_report_v1 is O(n^2) total: str has no __iadd__, so self.text = self.text + line + "\n" always calls str.__add__, which allocates a brand-new string and copies every character accumulated so far into it, on each of the n calls, so the copy costs sum to 1 + 2 + ... + n. build_report_v2 is O(n) total: join computes the total output length in one pass over rows, allocates one buffer of exactly that size, then copies each row into it once.

Both are O(n), because CPython over-allocates extra capacity for strings the same way it does for lists, so repeated concatenation is amortized O(1) per call just like append.

build_report_v1 is O(n) and build_report_v2 is O(n^2), because join scans rows twice (once to measure, once to copy), doubling its work compared to the single-pass loop in build_report_v1.