Complexity Analysis
def build_string(words):
result = ""
for w in words:
result += w
return resultWhat is the time and space complexity?
Work it out before scrolling down.
Time
O(n × k)
Space
O(n × k)
How to derive it
Trap: string concatenation in Python creates a new string each time. If there are n words of average length k, each concatenation copies the growing result. Total characters copied: k + 2k + 3k + ... + nk = k × n(n+1)/2 = O(n² × k). Use ''.join(words) for O(n × k). CPython has an optimization that sometimes makes += O(1) amortized, but you cannot rely on it.