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
– Telastyn, Commented Jan 2, 2021 at 16:44
Does this answer your question? What is O(...) and how do I calculate it? — gnat
– gnat, Commented Jan 2, 2021 at 23:20

Nat · Accepted Answer · 2021-01-02 17:33:08Z

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 2, 2021 at 17:33

answered Jan 2, 2021 at 17:01

Nat

1,1011 gold badge8 silver badges12 bronze badges

What do you mean minus the optimizations - what optimization is missing in your code?

user93353
– user93353

2021-01-03 02:39:09 +00:00
Commented Jan 3, 2021 at 2: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
– Nat

2021-01-06 12:14:34 +00:00
Commented Jan 6, 2021 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
– Nat

2021-01-06 12:20:50 +00:00
Commented Jan 6, 2021 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
– Nat

2021-01-06 12:27:54 +00:00
Commented Jan 6, 2021 at 12:27

Add a comment |

Stack Exchange Network

What is the time complexity of this algorithm

1 Answer 1

Your Answer

Linked

Hot Network Questions

What is the time complexity of this algorithm

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions