Strings

Strings are basically arrays of integers that map to ASCII characters. ASCII has less that 256 characters so each character takes less than 1 byte. In most languages, strings are immutable so some operations are more expensive than a dynamic array. Any mutation of the string will require a full reconstruction of the string.

Complexity

• Traverse: O(n)
• Copying: O(n)
• Getting at index: O(1)

Because strings are immutable in most languages (C++ is a notable exception), the below example will be O(n^2) because it will need to recreate the string every time it appends a character.

string = "this is a string"
newString = ""

for char in string:
    newString += char