Parsing numeric arguments - Time & Space Complexity

Time Complexity: Parsing numeric arguments

O(n)

Understanding Time Complexity

When parsing numbers from strings, it is important to know how the time needed grows as the input gets longer.

We want to find out how the work changes when the number has more digits.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int parseNumber(const char *str) {
    int result = 0;
    for (int i = 0; str[i] != '\0'; i++) {
        if (str[i] < '0' || str[i] > '9') break;
        result = result * 10 + (str[i] - '0');
    }
    return result;
}
    

This code reads a string character by character and converts the digits into an integer number.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop that reads each character in the string.
• How many times: Once for each character until a non-digit or end of string is found.

How Execution Grows With Input

As the number of digits in the string grows, the loop runs longer, doing more work.

Input Size (n)	Approx. Operations
10	About 10 loop steps
100	About 100 loop steps
1000	About 1000 loop steps

Pattern observation: The work grows directly with the number of digits; double the digits means double the steps.

Final Time Complexity

Time Complexity: O(n)

This means the time to parse grows in a straight line with the length of the input string.

Common Mistake

[X] Wrong: "Parsing a number always takes constant time because numbers are small."

[OK] Correct: The time depends on how many digits the number has, not the value itself. Longer numbers take more steps.

Interview Connect

Understanding how parsing time grows helps you write efficient input handling and shows you can think about performance clearly.

Self-Check

"What if we changed the code to parse hexadecimal numbers instead of decimal? How would the time complexity change?"