Query in java String complexity

1

Hi can any java user tell what is the time complexity of += operator for string concatenation in java ? O(n^2) or O(n)

2

Each call to .concat() or += is O(n), where n is the current length of the string.

3

Okay, so if I concatenate 2 strings A and B of length N and M respectively. And If I do the operation:

A+=B

then it would have a complexity of O(NM) right ?

4

No, sorry - I should refine my original statement: given such A and B, the complexity of

A += B is O(N + M).

5

Okay I see, can you suggest a way to add a character to the end of a string in O(1) time in java without using stringBuilder?

6

I’m not a Java guy, but no, I can’t see a way to add a char to an arbitrary java.lang.String in O(1).

1 Like
7

Okay thanks for replying :slight_smile:

1 Like
8 
String s="Jav"; char c='a';
s=s+""+c; //s="Java"

An example to add a character at the end.