Determine asymptotic complexity of the code

Question

I need to determine asymptotic complexive.

PROGRAM(A,n,x):
begin
    l:=0
    r:=n-1
    while TRUE do
        while l<r and A[l]<x do
            l:=l+1
        end
        while l<r and A[l]>=x do
           r:=r-1
        end
        if l>=r then
            return 
        end
        tmp:=A[l];
        A[l]:=A[r];
        A[r]:=tmp;
    end
end

Assumption that $A$ is array with $n$ integers and first element has index = 0

Please can you give me any hints?

Answer 1

The function is clearly trying to make sure that all elements that are less that $x$ are on the left hand side, and all elements greater than $x$ are on the right hand side.

To do this, it scans from left-to-right with the index $l$, looking for the index $A[l]$ where $A[l] > x$.

Similarly, it scans right-to-left with the index $r$, looking for a $A[r]$ such that $A[r] < x$

Knowing this, we can design the worst case input. For example, for an array of length $n$, the worst case wold be where:

1. $l$ would have to look till $n- 1$ from $0 \to n - 1$
2. $r$ would have to look till $0$ from $n - 1 \to 0$

Hence, an input maybe like $$S = [x - 1, x, x, x, \ldots, x + 1]$$

1. For this input $S$, $l$ will have to go to the $n-1$th index to find the $x + 1$ element which is greater than $x$. This is one search of length $n$

2. By a similar argument, $r$ will have a search of length $n$ from $n-1 \to 0$ to find the $x - 1$

If we consider our basic operator to be comparisons $<$ and $>$ that are done in the loop:

1. there are $n$ $<$ comparisons for $l$
2. there are $n$ $>$ comparisons for $r$.

Hence, the total search for a list of length $n$ in $2n$, which is in $\Theta(n)$

Hence, the algorithm is in $\Theta(n)$