String to Integer atoi in DSA Python - Time & Space Complexity

Time Complexity: String to Integer atoi

O(n)

Understanding Time Complexity

We want to understand how the time taken to convert a string to an integer grows as the string gets longer.

Specifically, how does the number of steps change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def myAtoi(s: str) -> int:
    i, n = 0, len(s)
    while i < n and s[i] == ' ':
        i += 1
    sign = 1
    if i < n and s[i] in ['+', '-']:
        sign = -1 if s[i] == '-' else 1
        i += 1
    result = 0
    while i < n and s[i].isdigit():
        result = result * 10 + (ord(s[i]) - ord('0'))
        i += 1
    return sign * result
    

This code converts a string to an integer by skipping spaces, handling sign, and reading digits.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two while loops scanning characters in the string.
• How many times: Each loop runs at most once over the string characters, total scanning each character at most once.

How Execution Grows With Input

The code scans the string from start to end, checking characters one by one.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The number of steps grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert the string grows linearly with the length of the input string.

Common Mistake

[X] Wrong: "The time complexity is constant because we only read until the first non-digit character."

[OK] Correct: In the worst case, the entire string can be digits, so the code must check every character, making time grow with input size.

Interview Connect

Understanding this linear time complexity helps you explain how your solution scales with input size, a key skill in interviews.

Self-Check

"What if the input string was given as a linked list of characters instead of a string? How would the time complexity change?"