Operation | String | StringBuffer | Rope | Trie |
---|---|---|---|---|
Access by Index | O(1) | O(n) | O(log n) | N/A |
Append | O(n) | O(1)* | O(log n) | O(m)** |
Concatenation | O(n+m) | O(1)* | O(log n) | N/A |
Substring | O(k) | O(n) | O(log n) | N/A |
Find/Search | O(nm)** | O(n*m) | O(n) | O(m) |
Insert | O(n) | O(1)* | O(log n) | O(m) |
Delete | O(n) | O(n) | O(log n) | O(m) |
Implementation | Space Complexity | Additional Notes |
---|---|---|
String | O(n) | Immutable, requires new copy for changes |
StringBuffer | O(n) | Mutable, grows dynamically |
Rope | O(n) | Additional O(log n) for tree structure |
Trie | O(ALPHABET_SIZE * m * n) | Where m is average string length |