What is Big O notation?

Big O notation is used to describe the complexity, i.e. performance, of an algorithm in Computer Science. Big O notation describes the worst-case scenario of an algorithm. Analysis of algorithms includes time complexity (i.e. how long will the algorithm take to execute) as well as space complexity (i.e. how much disk space or memory will the algorithm take to execute). Big O notation can be used to describe both time complexity as well as space complexity of algorithms.

Big O notation is depicted as O(g(N)) where g(N) is the order of growth for N data elements. Common order of growth scenarios encountered frequently are - constant (1), linear (N), logarithmic (log N), linearithmic (N log N), quadratic (N^2), cubic (N^3) and exponential (2^N). These are depicted in Big O notation as O(1), O(N), O(log N), O(N log N), O(N^2), O(N^3), O(2^N) respectively

Give example of an algorithm that takes constant time O(1) to complete.

Algorithms that take contact time O(1) are those algorithms that will take the same time (or space) to execute regardless of the size of the input data set.

Example: Algorithm to find the first element of an array - will always take the same time to execute regardless of the size of the size of the input dataset.

return myArray[0];

Give example of an algorithm that takes linear time O(N) to complete.

Algorithms that take linear time O(N) are Algorithms whose time to execute will grow linearly in proportion to the size of the input dataset. These are algorithms that will loop through the input dataset once.

Example - Algorithm to find the max value in an array of integers.

int maxValue = intArray[0],
for(int i=1; i < intArray.length; i++){ 
 if (a[i] > max) max = intArray[i];
}

Give an example of an algorithm that takes logarithmic time O(log N) to complete.

Algorithms that take logarithmic time O(log N) to complete are Algorithms that will grow logarithmically to the size of the input dataset. These are usually divide in half algorithms that will iteratively split the input dataset into two.

Example - Binary Search.

// A recursive binary search function.
// returns location of x in an array if present, else returns -1
int binarySearch(int myArray[], int l, int r, int x) {
 if (r >= l) { 
  int mid = l + (r - l)/2;

  //element present at the middle
  if (myArray[mid] == x) return mid;

  //element smaller than mid
  if (myArray[mid] > x) return binarySearch(myArray, l, mid-1, x);

  //element larger tham mid
  if (myArray[mid] < x) return binarySearch(myArray, mid+1, r, x);
 }
 //element not present in array
 return -1;
}

Give an example of an algorithm that takes linearithmic time O(N log N) to complete.

Algorithms that take linearithmic time O(N log N) time to complete are Algorithms that are usually divide and conquer algorithms which will iteratively split the input dataset into two.

Example - Sorting Algorithm - Mergesort.

Give an example of an algorithm that takes quadratic time O(N^2) to complete.

Algorithms that take quadratic time O(N^2) to complete are Algorithms that require double loops, i.e. loop within a loop.

Example: Algorithm to get all pairs of an array's elements.

for (int i=0; i < myArray.length; i++) {
 for (int j=i+1; j < myArray.length; j++) {
  System.out.println(myArray[i]+myArray[j]);
 }
}

Give an example of an algorithm that takes cubic time O(N^3) to complete.

Algorithms that take cubic time O(N^3) to complete are Algorithms that require triple loops, i.e. loop -within a loop -within a loop.

Example: Algorithm to get all triples of an array's elements.

for (int i=0; i < myArray.length; i++) {
 for (int j=i+1; j < myArray.length; j++) {
  for (int k=j+1; k < myArray.length; k++) {
   System.out.println(myArray[i]+myArray[j]+myArray[k]);
  }
 }
}

Give an example of an algorithm that takes exponential time O(2^N) to complete.