Dutch National Flag Three Way Partition in DSA Python - Time & Space Complexity

Time Complexity: Dutch National Flag Three Way Partition

O(n)

Understanding Time Complexity

We want to understand how the time needed to sort colors using the Dutch National Flag method changes as the list grows.

How does the number of steps grow when we have more items to sort?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    def dutch_national_flag(arr):
        low, mid, high = 0, 0, len(arr) - 1
        while mid <= high:
            if arr[mid] == 0:
                arr[low], arr[mid] = arr[mid], arr[low]
                low += 1
                mid += 1
            elif arr[mid] == 1:
                mid += 1
            else:
                arr[mid], arr[high] = arr[high], arr[mid]
                high -= 1
    

This code sorts an array containing 0s, 1s, and 2s by grouping them in order.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves mid pointer through the array.
• How many times: Each element is visited at most once by mid, so up to n times where n is array length.

How Execution Grows With Input

As the array size grows, the number of steps grows roughly the same way because each element is checked once.

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

Pattern observation: The work grows linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to sort grows directly in proportion to the number of items.

Common Mistake

[X] Wrong: "Because there are nested ifs, the time is O(n²)."

[OK] Correct: The loop runs once per element, and swaps happen in constant time, so no nested loops cause repeated full passes.

Interview Connect

Knowing this linear time sorting method shows you can handle problems efficiently and is a great skill to demonstrate.

Self-Check

"What if the array contained more than three distinct values? How would the time complexity change?"