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

Time Complexity: String to Integer atoi

O(n)

Understanding Time Complexity

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

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.

int myAtoi(char * s) {
    int i = 0, sign = 1, result = 0;
    while (s[i] == ' ') i++;
    if (s[i] == '-' || s[i] == '+') {
        sign = (s[i] == '-') ? -1 : 1;
        i++;
    }
    while (s[i] >= '0' && s[i] <= '9') {
        result = result * 10 + (s[i] - '0');
        i++;
    }
    return sign * result;
}
    

This code converts a string to an integer by skipping spaces, handling sign, and reading digits until a non-digit is found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The two while loops that scan characters in the string.
• How many times: Each loop runs at most once over parts of the string, together covering up to all characters.

How Execution Grows With Input

As the string length grows, the code checks each character once until it stops at a non-digit or end.

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 input size.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "The function runs in constant time because it just converts a number."

[OK] Correct: The function must check each character until it finds a non-digit, so time depends on string length.

Interview Connect

Understanding this helps you explain how simple string processing scales, a common skill in coding interviews.

Self-Check

"What if the input string is guaranteed to have only digits and no spaces or signs? How would the time complexity change?"