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

Time Complexity: Dutch National Flag Three Way Partition

O(n)

Understanding Time Complexity

We want to know how the time taken by the Dutch National Flag algorithm changes as the input size grows.

Specifically, how many steps does it take to rearrange the array into three parts?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void dutchFlagPartition(int arr[], int n, int pivot) {
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (arr[mid] < pivot) {
            int temp = arr[low]; arr[low] = arr[mid]; arr[mid] = temp;
            low++; mid++;
        } else if (arr[mid] == pivot) {
            mid++;
        } else {
            int temp = arr[mid]; arr[mid] = arr[high]; arr[high] = temp;
            high--;
        }
    }
}
    

This code rearranges the array so that all elements less than pivot come first, then equal to pivot, then greater than pivot.

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 the mid pointer.

How Execution Grows With Input

As the array size grows, the number of steps grows roughly the same as the number of elements.

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

Pattern observation: The steps increase linearly with input size.

Final Time Complexity

Time Complexity: O(n)

This means the time to rearrange grows directly in proportion to the number of elements.

Common Mistake

[X] Wrong: "Because there are nested if-else checks inside the loop, the time complexity is O(n²)."

[OK] Correct: The loop runs only once through the array, and each element is handled a limited number of times, so the total steps grow linearly, not quadratically.

Interview Connect

Understanding this linear time partitioning is a key skill for array problems and shows you can handle multiple conditions efficiently in one pass.

Self-Check

"What if we changed the algorithm to use two separate passes instead of one? How would the time complexity change?"