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

Time Complexity: Roman to Integer Conversion

O(n)

Understanding Time Complexity

We want to understand how the time needed to convert a Roman numeral to an integer changes as the length of the Roman numeral grows.

Specifically, how does the number of steps grow when the input string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def roman_to_int(s: str) -> int:
    roman_map = {'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
    total = 0
    for i in range(len(s)):
        value = roman_map[s[i]]
        if i + 1 < len(s) and roman_map[s[i]] < roman_map[s[i + 1]]:
            total -= value
        else:
            total += value
    return total
    

This code converts a Roman numeral string into its integer value by checking each character and deciding whether to add or subtract its value.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the input string once.
• How many times: Exactly once for each character, so as many times as the length of the string.

How Execution Grows With Input

As the Roman numeral string gets longer, the number of steps grows directly with its length.

Input Size (n)	Approx. Operations
10	About 10 checks and additions/subtractions
100	About 100 checks and additions/subtractions
1000	About 1000 checks and additions/subtractions

Pattern observation: The work grows evenly and directly with the input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to convert grows in a straight line with the length of the Roman numeral string.

Common Mistake

[X] Wrong: "Because there is a nested if inside the loop, the time complexity is quadratic O(n²)."

[OK] Correct: The if condition is inside a single loop and does not cause extra loops; it only checks the next character once, so the overall work is still proportional to n.

Interview Connect

Understanding this linear time complexity helps you explain how your solution scales well with input size, a key skill interviewers look for.

Self-Check

"What if we used recursion to process each character instead of a loop? How would the time complexity change?"