Roman to Integer Conversion in DSA C - Time & Space Complexity

Time Complexity: Roman to Integer Conversion

O(n)

Understanding Time Complexity

We want to know how the time to convert a Roman numeral to an integer changes as the input gets longer.

How does the number of steps grow when the Roman numeral string grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int romanToInt(char * s) {
    int total = 0;
    int i = 0;
    while (s[i]) {
        int current = value(s[i]);
        int next = value(s[i + 1]);
        if (next > current) {
            total += (next - current);
            i += 2;
        } else {
            total += current;
            i++;
        }
    }
    return total;
}

int value(char c) {
    switch(c) {
        case 'I': return 1;
        case 'V': return 5;
        case 'X': return 10;
        case 'L': return 50;
        case 'C': return 100;
        case 'D': return 500;
        case 'M': return 1000;
        default: return 0;
    }
}
    

This code converts a Roman numeral string to an integer by checking each character and sometimes the next one.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that goes through each character in the string.
• How many times: It runs once for each character, sometimes skipping one extra character when two are processed together.

How Execution Grows With Input

As the Roman numeral string gets longer, the number of steps grows roughly the same as the string length.

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

Pattern observation: The steps increase linearly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows directly with the length of the Roman numeral string.

Common Mistake

[X] Wrong: "Because we sometimes skip characters, the time is less than linear or constant."

[OK] Correct: Even when skipping, each character is still checked once, so the total work grows with the input size.

Interview Connect

Understanding how to analyze simple loops like this helps you explain your code clearly and shows you know how input size affects performance.

Self-Check

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