Suppose that a and b are n-character Strings. what is the complexity of performing a=a+b?

Question

Suppose that a and b are n-character Strings. what is the complexity of performing a=a+b?

my answer is O(n) but i am not sure if this is correct.

Answer 1

It depends on how your strings are stored, assuming $+$ is concatenation. If your strings are stored as linked lists of characters and you know the beginning and end of each list, then the complexity is $O(1)$ because you make the end node of the list for $a$ point to the beginning node of the list for $b$. (Assuming it's ok to resuse memory when creating $a+b$). If they are stored as arrays so that you need to create a new array for $a+b$ and copy over, then it's $O(n)$ (linear in the sum of lengths of the two strings).