What is the time complexity of this algorithm

Question

This code is from https://www.geeksforgeeks.org/segregate-even-and-odd-numbers/

It takes an array of numbers & segregates them in place without bothering about the order.

void segregateEvenOdd(int arr[], int size)
{
    /* Initialize left and right indexes */
    int left = 0, right = size-1;
    while (left < right)
    {
        /* Increment left index while we see 0 at left */
        while (arr[left] % 2 == 0 && left < right)
            left++;

        /* Decrement right index while we see 1 at right */
        while (arr[right] % 2 == 1 && left < right)
            right--;

        if (left < right)
        {
            /* Swap arr[left] and arr[right]*/
            swap(&arr[left], &arr[right]);
            left++;
            right--;
        }
    }
}

The site mentions that this algorithm is O(n).

However, since there is an inner loop and an other loop, I don't think this is O(n). Since the inner loop doesn't run through for each iteration of the other loop, it's not O(n^2) either.How does one analyse the complexity of this algorithm? I think it's an O(nlogn) algorithm but I am not sure how to arrive at that?

Answer 1

It's basically just one loop that scans from left and right to a midpoint.

Here's a simpler version that does the same thing (though omits optimizations):

void segregateEvenOdd(int arr[], int size)
{
    int left  = 0;
    int right = size - 1;

    while (left < right)
    {
        if (arr[left] % 2 == 0)
        {
            left++;
        }
        else if (arr[right] % 2 == 1)
        {
            right--;
        }
        else
        {
            swap(&arr[left], &arr[right]);
        }
    }
}

Or in tabular form:

void segregateEvenOdd(int arr[], int size)
{
    int left  = 0;
    int right = size - 1;

    while (left < right)
    {
        if      (arr[left]  % 2 == 0) { left++;                        }
        else if (arr[right] % 2 == 1) { right--;                       }
        else                          { swap(&arr[left], &arr[right]); }
    }
}

So the claim that it's O(n) makes sense, where n is the size of the loop and presumably other operations are assumed to be O(1).