How do you calculate big O of an algorithm

Question

I have a problem where i have to find missing numbers within an array and add them to a set.

The question goes like so:

Array of size (n-m) with numbers from 1..n with m of them missing.

Find one all of the missing numbers in O(log). Array is sorted. Example:

n = 8

arr = [1,2,4,5,6,8]

m=2

Result has to be a set {3, 7}.

This is my solution so far and wanted to know how i can calculate the big o of a solution. Also most solution I have seen uses the divide and conquer approach. How do i calculate the big oh of my algorithm below ?

ps If i don't meet the requirement, Is there any way I can do this without having to do it recursively ? I am really not a fan of recursion, I simply cant get my head around it ! :(

var arr = [1,2,4,5,6,8];
var mySet = [];

findMissingNumbers(arr);

function findMissingNumbers(arr){
    var temp = 0;
    for (number in arr){                    //O(n)
        temp = parseInt(number)+1;
        if(arr[temp] - arr[number] > 1){
            addToSet(arr[number], arr[temp]);
        }
    }
}

function addToSet(min, max){

    while (min != max-1){
        mySet.push(++min);
    }
}

Answer 1

There are two things you want to look at, one you have pointed out: how many times do you iterate the loop "for (number in arr)"? If you array contains n-m elements, then this loop should be iterated n-m times. Then look at each operation you do inside the loop and try to figure out a worst-case scenario (or typical) scenario for each. The temp=... line should be a constant cost (say 1 unit per loop), the conditional is constant cost (say 1 unit per loop) and then there is the addToSet. The addToset is more difficult to analyze because it isn't called every time, and it may vary in how expensive it is each time called. So perhaps what you want to think is that for each of the m missing elements, the addToSet is going to perform 1 operation... a total of m operations (which you don't know when they will occur, but all m must occur at some point). Then add up all of your costs.

n-m loops iterations, in each one you do 2 operations total of 2(n-m) then add in the m operations done by addToSet, for a total of something like 2n-m ~ 2n (assuming that m is small compared to n). This could be O(n-m) or also O(n) (If it is O(n-m) it is also O(n) since n >= n-m.) Hope this helps.

Answer 2

In your code you have a complexity of O(n) in time because you check n index of your array. A faster way to do this is something like that :

• Go to the half of your array
• Is this number at the right place (this means the other ones will be too because array is sorted)
• If it's the expected number : go to the half of the second half
• If not : add this number in the set and go to the half of the first half
• Stop when the number you looking at is at index size-1

Note that you can have some optimization, for example you can directly check if the array have the correct size and return an empty array. It depends of your problem.

My algorithm is also in O(n) because you always take the worst set of data. In my case I would be that we miss one data at the end of the array. So technically it should be O(n-1) but constants are negligible in front of n (assumed to be very high). That's why you have to keep in mind the average complexity too.

Answer 3

For what it's worth here is a more succinct implementation of the algorithm (javascript):

var N = 10;
var arr = [2,9];
var mySet = [];
var index = 0;
for(var i=1;i<=N;i++){
    if(i!=arr[index]){
        mySet.push(i);
    }else{
        index++;
    }
}

Here the big(O) is trivial as there is only a single loop which runs exactly N times with constant cost operations each iteration.

Answer 4

Big O is the complexity of the algorithm. It is a function for the number of steps it takes your program to come up with a solution.

This gives a pretty good explanation of how it works:

Big O, how do you calculate/approximate it?