Time Complexity: String slicing and indexing
O(k)
0
0
String slicing and indexing in Ruby - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time it takes to get parts of a string changes as the string gets bigger.
How does slicing or picking characters from a string grow with the string size?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
str = "hello world"
slice = str[2..5]
char = str[4]
This code takes a part of the string from index 2 to 5 and also picks a single character at index 4.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Extracting a substring by copying characters from the original string.
- How many times: The number of characters copied equals the length of the slice requested.
How Execution Grows With Input
When you ask for a slice of length k, the program copies k characters. So the time depends on how big the slice is, not the whole string.
| Input Size (n) | Approx. Operations for slice length k |
|---|---|
| 10 | Copy k characters (e.g., 4) |
| 100 | Copy k characters (still 4 if slice length same) |
| 1000 | Copy k characters (still 4 if slice length same) |
Pattern observation: Time grows with the slice length, not the total string length.
Final Time Complexity
Time Complexity: O(k)
This means the time depends on how many characters you want to get, not how long the whole string is.
Common Mistake
[X] Wrong: "Getting a single character from a string takes time proportional to the whole string length."
[OK] Correct: Accessing one character by index is very fast and does not depend on string size; it is a direct lookup.
Interview Connect
Knowing how string slicing works helps you write efficient code when working with text, which is common in many programming tasks.
Self-Check
"What if we sliced the entire string instead of a small part? How would the time complexity change?"