Complexity of insert(0, c) operation on StringBuffer: is it O(1)?

The insert operation on a StringBuffer is O(n). This is because it must shift up to n characters out of the way to make room for the element to be inserted.

"bc"
insert(0, 'a') => "_bc" => "abc"

You can get around this by not using insert. You can iterate the letters in the reverse order, and then you can call the O(1) append method.

The StringBuffer class is a subclass of AbstractStringBuilder, which defines a char[] to hold the characters. It uses System.arraycopy to move the existing characters out of the way on a call to insert.

Well, it's an implementation detail - but I wouldn't expect it to be a linked list of characters. I'd expect it to be a char[] with a length, basically - like an ArrayList, but for characters. So inserting a character at the start of the buffer means copying all the rest of the data.

That's been the basis of every implementation I've seen - a linked list of characters would have huge memory (and allocation time) costs compared with the more common implementation. A list or tree structure comprising of references to portions of strings (see "rope") wouldn't have the same costs, but I haven't personally seen a Java implementation of java.lang.StringBuilder or java.lang.StringBuffer which uses ropes. So yes it is O(n) at least almost always.