Big-Oh designation for a single cycle spanning two halves of an array with two iterative vars

Question

Trying to figure out my understanding of Big-O for a test (a very basic understanding of Big-O is required). I got up and did 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 of which covers half the array with a fixed amount of work (which, I think, calls them like in O (n / 2))

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

Now, please forgive me, because this is my real understanding, and it was my attempt to solve the problem. I found many big-o examples online, but none of them are like it, where iterators simultaneously grow and modify the array at the same time.

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

Could someone clarify this for me?

thanks

Answer 1

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

It is right. Not because it makes one cycle, but because it is one cycle, which depends on the size of the array by a constant coefficient: a large O note ignores any constant factor. O(n) means that the only effect on the algorithm is based on the size of the array. Just because it actually takes half the time doesn't matter for large O.

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

Otherwise, if the size of the cycle changes differently than a constant, but as a logarithmic or exponential function n , for example, if size 100 and cycle 2 , size 1000 and loop 3 , size 10000 and cycle 4 . In this case, it will be, for example, O(log(n)) .

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

I was also wondering if the equation I came across to get there, somewhere on the football field, to be correct, was obtained.

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

Answer 2

You are right about the cycle. Loop will detect Big O. But the loop only works for half the array.

So him. 2 + 6 * (n / 2)

If we make n very large, the other numbers are really small. Therefore, they will not matter. So its O (n).

Let's say you use 2 separate loops. 2 + 6 * (n / 2) + 6 * (n / 2) . In this case, there will again be O (n).

But if we run a nested loop. 2+ 6 * (n * n) . Then it will be O (n ^ 2)

Always remove constants and do the math. You have an idea.

Answer 3

As ji decreases by 2 units at each iteration, N/2 are taken from them (assuming N=length(a) ).

Therefore, the run time is indeed O(N/2) . And O(N/2) strictly equivalent to O(N) .