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?"

Practice

1. What does the atoi function do in C programming?

easy

A. Checks if a string contains only digits

B. Converts a string representing a number into an integer

C. Calculates the length of a string

D. Converts an integer into a string

Solution

1. Step 1: Understand the purpose of atoi

   The atoi function stands for ASCII to integer, which means it converts a string of digits into an integer value.

2. Step 2: Compare options with definition

   Only Converts a string representing a number into an integer correctly describes this conversion from string to integer.

3. Final Answer:

   Converts a string representing a number into an integer -> Option B

4. Quick Check:

   atoi = string to integer conversion [OK]

Hint: Remember atoi means ASCII to integer conversion [OK]

Common Mistakes:

• Confusing atoi with itoa (integer to ASCII)
• Thinking atoi calculates string length
• Assuming atoi validates string digits

2. Which of the following is the correct syntax to use atoi in C?

easy

A. int num = atoi(char *str);

B. int num = atoi();

C. int num = atoi(int str);

D. int num = atoi(str);

Solution

1. Step 1: Check function parameter type

   The atoi function takes a single argument of type const char *, which is a string pointer.

2. Step 2: Validate correct syntax

   int num = atoi(str); correctly shows calling atoi with a string variable str without specifying type in call.

3. Final Answer:

   int num = atoi(str); -> Option D

4. Quick Check:

   atoi takes string variable as argument [OK]

Hint: Call atoi with just the string variable name [OK]

Common Mistakes:

• Including type in function call parentheses
• Calling atoi without arguments
• Passing integer instead of string

3. What will be the output of the following C code?

char str[] = "-123abc";
int val = atoi(str);
printf("%d", val);

medium

A. -123

B. 0

C. 123

D. Error

Solution

1. Step 1: Analyze atoi behavior with mixed string

   atoi converts initial numeric part including sign until non-digit character. Here, "-123" is converted, stops at 'a'.

2. Step 2: Determine output value

   So, val becomes -123 and printf prints -123.

3. Final Answer:

   -123 -> Option A

4. Quick Check:

   atoi stops at first non-digit, returns -123 [OK]

Hint: atoi reads number until first non-digit character [OK]

Common Mistakes:

• Expecting atoi to ignore leading sign
• Thinking atoi returns 0 on trailing letters
• Assuming runtime error due to letters

4. Identify the error in this code snippet using atoi:

char *str = NULL;
int num = atoi(str);
printf("%d", num);

medium

A. Passing NULL pointer to atoi causes undefined behavior

B. Missing header file

C. atoi cannot convert strings with digits

D. No error, code runs fine

Solution

1. Step 1: Check argument passed to atoi

   The code passes a NULL pointer to atoi, which expects a valid string pointer.

2. Step 2: Understand consequences of NULL argument

   Passing NULL leads to undefined behavior, often causing a crash or runtime error.

3. Final Answer:

   Passing NULL pointer to atoi causes undefined behavior -> Option A

4. Quick Check:

   atoi needs valid string pointer, NULL causes error [OK]

Hint: Never pass NULL to atoi; always check string pointer [OK]

Common Mistakes:

• Ignoring NULL pointer checks
• Assuming atoi handles NULL safely
• Confusing missing header with runtime error

5. You want to convert a string to integer but also detect if the string contains invalid characters after the number. Which approach is best in C?

hard

A. Use atoi and then check the rest of the string manually

B. Use atoi and assume input is always valid

C. Use strtol which provides end pointer to check leftover characters

D. Use printf to convert string to integer

Solution

1. Step 1: Understand limitation of atoi

   atoi converts initial number but does not provide info about leftover invalid characters.

2. Step 2: Use strtol for better control

   strtol converts string to long and returns pointer to first invalid character, allowing validation.

3. Step 3: Choose best approach

   Use strtol which provides end pointer to check leftover characters uses strtol with end pointer to detect invalid trailing characters safely.

4. Final Answer:

   Use strtol which provides end pointer to check leftover characters -> Option C

5. Quick Check:

   strtol + end pointer = safe string to int with validation [OK]

Hint: Use strtol with end pointer to detect invalid chars [OK]

Common Mistakes:

• Relying only on atoi for input validation
• Ignoring leftover characters after number
• Using printf incorrectly for conversion