Core Concept Mastery • DSA Module
String operations have O(n) time complexity because you must traverse the string character by character. Space complexity is O(n) because strings grow linearly with the number of characters.
Think of reading a book: Time = O(n) because you read each page (character). Space = O(n) because a longer book takes more shelf space (memory).
| Operation | Time | Space | Why? |
|---|---|---|---|
| Length | O(n) | O(1) | Walk until \\0 |
| Compare | O(n) | O(1) | Check every letter |
| Concatenate | O(n) | O(n) | Find end → Copy |
| Copy | O(n) | O(n) | Copy each char |
| Storage | - | O(n) | n chars + \\0 |
Storing "ABC":
Takes 4 bytes: 3 characters + 1 terminator
Space Complexity: O(n) where n = number of characters
Let's break down why strings have these complexities.
Time Complexity — The Walking Cost
Most string operations require "walking" through the string:
Why O(n)? Because strings don't store their length. You must check each character until you find \0. Even if you know the length, operations like compare or copy still need to process each character.
Space Complexity — The Memory Cost
Space complexity is straightforward:
Real-World Impact
Optimization Tips
Understanding complexity helps you predict performance. If you're processing millions of strings, O(n) operations can become slow. This knowledge helps you optimize your code.
"What is the time complexity of most string operations?"
O(n), where n is the length of the string. This is because strings don't store their length and operations must traverse character by character until finding \0.