How to find the formula of best case and worst cas

Question

I was given a task. Write an algorithm so that, the input of 2 lists of data, will have at least one in common.

So, this is my algorithm: (I write the code in php)

$arrayA = array('5', '6', '1', '2', '7');
$arrayB = array('9', '2', '1', '8', '3');
$arrayC = array();

foreach($arrayA as $val){
    if(in_array($val, $arrayB)){
        array_push($arrayC, $val);
    }
}

Thats my own algo, not sure if its a good one. So, based on my algorithm, how to find the formula of best case and worst case (big O)?

Note: Please do let me know, if my algorithm is wrong. My goal is " input of 2 lists of data, will have at least one in common."

Answer 1

worst case can be found by assuming that both lists have an element in common and it's the last one on each list: this will lead to going through the first list by checking all elements of the second (you are using in_array but assume you do it by hand, it's the same thing O(m): complexity).

So you are going n times through the second list, complexity will be O(n*m) where n is the length of the first list and m the length of the second..

To find average complexity you should consider a solution that is average with respect to what you are computing.. it's quite easy and I leave it as an exercise.

Answer 2

When dealing with this kind of algorithmic problems you have to consider lists from an 'algorithmic' point of view. That is, a datatype with a little set of O(1) operations supported. Usually like below:

• check if the list is empty
• append an item at the end of list
• get the first element of the list
• remove the first element from the list

The idea is to express what is asked using only the above operators, then all you have to do is multiply the number of times a loop is executed by the complexity of what is inside it.

Be very careful when writing code in an evolved programming languages instead of writing an algorithm, as it hides complexity (@FrustratedWithFormsDesign allready hinted on this).

Answer 3

To get you started:

1. Do you have any explicit loops? If so, how many times will they run (max, min, avg)?
2. Do you have any implicit loops? If so, how many times will they run (max, min, avg)?
3. Are any of these loops nested? If so, do they depend on each other? In what ways are they dependent