String Reversal Approaches in DSA Python - Time & Space Complexity

Time Complexity: String Reversal Approaches

O(n^2)

Understanding Time Complexity

We want to understand how the time needed to reverse a string changes as the string gets longer.

How does the work grow when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def reverse_string(s: str) -> str:
    result = []
    for char in s:
        result.insert(0, char)
    return ''.join(result)

This code reverses a string by inserting each character at the start of a list, then joining the list into a string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over each character in the string and inserting it at the start of the list.
• How many times: Once for each character in the string (n times).

How Execution Grows With Input

Each insertion at the start shifts existing elements, so work grows faster than just the number of characters.

Input Size (n)	Approx. Operations
10	About 55 (sum of 1 to 10)
100	About 5,050
1000	About 500,500

Pattern observation: Operations grow roughly with the square of the input size.

Final Time Complexity

Time Complexity: O(n2)

This means the time needed grows roughly with the square of the string length because each insert shifts elements.

Common Mistake

[X] Wrong: "Inserting at the start of a list is a quick, constant-time operation like appending at the end."

[OK] Correct: Inserting at the start requires moving all existing elements one step, so it takes longer as the list grows.

Interview Connect

Understanding how different ways to reverse a string affect time helps you choose the best method in real problems.

Self-Check

"What if we used a list to collect characters by appending at the end and then reversed the list once at the end? How would the time complexity change?"