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?

This is O(n) since left/right only move one at a time and necessarily touch every element. That said, discussing a post elsewhere is generally off topic here. — Telastyn, Jan 02 '21 at 16:44
Does this answer your question? [What is O(...) and how do I calculate it?](https://softwareengineering.stackexchange.com/questions/132331/what-is-o-and-how-do-i-calculate-it) — gnat, Jan 02 '21 at 23:20

Nat · Accepted Answer · 2021-01-02T17:33:08.250

2

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).

edited Jan 02 '21 at 17:33

answered Jan 02 '21 at 17:01

Nat

1,063
1
8
11

What do you mean `minus the optimizations` - what optimization is missing in your code? – user93353 Jan 03 '21 at 02:39
@user93353: I removed two. The simpler optimization was the inclusion of `swap(&arr[left], &arr[right]); left++; right--;`, which I reduced to `swap(&arr[left], &arr[right]);`, omitting the increment/decrement. The increment/decrement were optimizations in the sense that they weren't necessary for the code to do what it was intended to do, but exploited the programmer's knowledge about what would happen after the `swap()` to skip ahead in the process. – Nat Jan 06 '21 at 12:14
@user93353: The other optimization was the fragmentation of the `while()`-loop. For example, consider a case in which the loop performs the second branch, i.e. it found an odd-number on the right-hand-side, so it `right--;`'d. In the un-optimized version above, the code would again check if the current left-hand-side-value is even-or-not, even though it performed that check previously. By contrast, the optimized version quoted in the above question statement doesn't go back to the start of the main `while()`-loop, skipping this redundant check. – Nat Jan 06 '21 at 12:20
@user93353: To note it, sometimes optimizations can change an algorithm's complexity class, such that de-optimizing an algorithm could take it from O(n) to something else. However, the de-optimized versions are also O(n). – Nat Jan 06 '21 at 12:27

What is the time complexity of this algorithm

1 Answers1