Big-Oh notation for a single while loop covering two halves of an array with two iterator vars

Question

Trying to brush up on my Big-O understanding for a test (A very basic Big-O understanding required obviously) I have coming up and was doing some practice problems in my book.

They gave me the following snippet

public static void swap(int[] a)
{
    int i = 0;
    int j = a.length-1;

    while (i < j)
    {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
        i++;
        j--;
    }
}

Pretty easy to understand I think. It has two iterators each covering half the array with a fixed amount of work (which I think clocks them both at O(n/2))

Therefore O(n/2) + O(n/2) = O(2n/2) = O(n)

Now please forgive as this is my current understanding and that was my attempt at the solution to the problem. I have found many examples of big-o online but none that are quite like this where the iterators both increment and modify the array at basically the same time.

The fact that it has one loop is making me think it's O(n) anyway.

Would anyone mind clearing this up for me?

Thanks

Answer 1

The fact that it has one loop is making me think it's O(n) anyway.

This is correct. Not because it is making one loop, but because it is one loop that depends on the size of the array by a constant factor: the big-O notation ignores any constant factor. O(n) means that the only influence on the algorithm is based on the size of the array. That it actually takes half that time, does not matter for big-O.

In other words: if your algorithm takes time n+X, Xn, Xn + Y will all come down to big-O O(n).

It gets different if the size of the loop is changed other than a constant factor, but as a logarithmic or exponential function of n, for instance if size is 100 and loop is 2, size is 1000 and loop is 3, size is 10000 and loop is 4. In that case, it would be, for instance, O(log(n)).

It would also be different if the loop is independent of size. I.e., if you would always loop 100 times, regardless of loop size, your algorithm would be O(1) (i.e., operate in some constant time).

I was also wondering if the equation I came up with to get there was somewhere in the ballpark of being correct.

Yes. In fact, if your equation ends up being some form of n * C + Y, where C is some constant and Y is some other value, the result is O(n), regardless of whether see is greater than 1, or smaller than 1.