What is the Big-O? 

The big-o notation is a relative representation of the complexity of an algorithm. In simple words, it means that this annotation represents how much effort will be required to process a code. This representation is based on the relation of the operations versus the number of elements to be processed. (++Operations == ++time/effort to be processed)

Screen Shot 2018-01-19 at 10.55.47 AM

Following some code examples with few explanations.

  • O(1)

public in bigO(int N) {
    return n * n;
 }

The implementation has one step/operation and it never will be increased. No matter the value of the N the effort to process it will be always the same.

  • O(n)

public in bigO(int n) {
    int result = 0;
    while (n > 1) {
      n -=1;    
    }
    return result;
}

The effort to process it is directly proportional how much elements will be processed.

  • O(nˆ2)

public int bigO(int[] A) {
    int result = 0;
    for (int i = 0; i < A.length; i++) {
        for (int j = 0; j < A.length; j++) {
            result += A[i] + A[j];
        }
    }
    return result;
}

Here we have a loop inside another, which means that for each element added into the array the effort to get it processed will be increased exponentially.  For example, for 10 elements into the array, it will have 100 of processes and for 100 elements it will have 10.000 of processes to get be done. (N*N = nˆ2)

  • O(log n)

public in bigO(int n) {
    int result = 0;
    while (n > 1) {
      n = n/2;  
      result += 1
    }
    return result;
}

The  O(logn) is normally applied in the solutions which will do an operation and the elements will be always be divided or multiplied to find the expected result. For example, a solution to check if an item is contained in a list, where the items in the list will be sorted and for each interaction, this list will be divided and the process will continue until find the item into the half of the list picked up where the item could be. (n + 1/2 * 1/2  … = 1 AND 1 * 2 * 2  … =n)

 

 

 

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s