How to determine the best case and the worst case of a program (algorithm)?

Question

Suppose I have this program, I want to compare 2 input lists. Suppose array A and array B. How to determine the best case and worst case of a function?

Here is my code in [php]:

foreach($array_1 as $k){ if(!in_array($k, $array_2)){ array_push($array_2, $k); } } 

What is the best case and worst case of a for loop? Please add some explanation, thanks :)

Edition:

Since my goal is to compare 2 lists that have 1 item in the general list. I think my code is above. Here is my updated code

 foreach($array_1 as $k){ if(in_array($k, $array_2)){ array_push($array_3, $k); } } 

And I think it will be:

Best case: O (n)

In the worst case: O (N * M)

Answer 1

Then do a quick analysis:

 foreach($array_1 as $k) 

means that the operation inside will be repeated for each element of the array. Denote the size of the array by N

Operation inside:

 if (!in_array($k, $array_2)) { array_push($array_2, $k); } 

There are 2 operations here:

• in_array
• array_push

array_push is likely to be constant, thus O(1) , while in_array more likely to search array_2 in array_2 , which will take either 1 operation (found as the first element) up to the length of array_2 .

Note that in_array is the only variable here:

• best case: in_array returned on the first comparison -> all elements of array_1 match, and either array_2 was empty, or they were equal to its first element. The complexity is O(N) , since we have N elements in array_1
• worst case: every time we check each element of array_2 →, all elements from array_1 different and different from previous elements of array_2 . If M is the length of array_2 when it is entered, then the complexity goes along the line O(N * (N+M) ) , (N+M)/2 , which is the average time to search in array_2 as it increases from M to M+N , and the constant 2 discarded in the notation O

Hope this helps.

Answer 2

The Big O designation is all approximations. This simplifies the comparison of algorithms.

If you present your array of elements, the search can be in order N (you have to look at each element to find the element you need), it can be Log (N) order, if you have an ordered collection, or it can even be in order 1 depending on the type of your collection.

It is important to look at your algorithm and determine which key operations are repeated.

Foreach is obviously an operation of order N, by definition you should work with every element of your list. O (N)

Next is your if InArray 2. This is similar to searching through an array, which is likely to be unordered, so this will be order N (linear search). So your complexity will now be O (N * M). (for each n elements in array 1, search for complexity of order N in array 2).

Finally, you have an array. I do not know your environment, but it can be order 1 or order N, if the array needs to be redistributed and copied in order to grow. Let's assume order 1 is simple. So your complexity in Big O is O (N * M).

So, now it is best that each element finds it in the first attempt and performs a push of the array, which will be O (N * 1 * 1) = O (N).

In the worst case, each element cannot be found in the second list, forcing a complete search for all elements of array 2. Therefore, the complexity is O (N * M).

Your teachers want to understand your thinking, so show them your assumptions. I strongly recommend that you read the exact question and the information that was provided to you before relying on the assumptions given here, you may have been told a language / platform that will tell you the exact punishment and the algorithms used in each case. Hope that helps :)

Answer 3

As a rule, with such a problem, I simply consider the algorithm as "Doctor Evil" and ask: "How can I do this, perhaps the most time?"