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.

Recursion is an approach to solving algorithms by using a function that calls itself. This process in which a function calls itself is called recursion, and the function that calls itself is called a recursive function.

Write a function in Java that returns the factorial of a number n?

Factorial of a number n, written as 'n!', is the product of all positive numbers less than n.

Formula: n! = n*(n-1)*(n-2)*(n-3)*(n-4)...*1

Example of sequence: 4! = 4*3*2*1=24

Below function calculates the factorial for a number n using recursion.

public int factorial(int n) {
 //base condition
 if (n==0) {
  return 1;
 } else {
  //recursion
  return n*factorial(n-1);
 }
}

Write a function in Java that returns the factorial of a number n?

Fibonacci numbers are the numbers in the following integer sequence, called the Fibonacci sequence, and characterized by the fact that every number after the first two is the sum of the two preceding ones.

Formula: Fn = Fn-1 + Fn-2

Example of sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

function fibonacci(int n) {
 //base condition
 if (n <= 2) {
  return 1;
 }
 //recursion
 return fibonacci(n — 1) + fibonacci(n — 2);
}

How do you traverse a graph using Breadth First Search (BFS)?

In a Breadth First Search (BFS) traversal of a graph, you traverse all vertices at one level before moving on to the next level.

You start by traversing from any vertex say currentVertex. If adjacent vertices to the currentVertex are not yet visited then print their value. Then repeat the same for children of the currentVertex.

How do you traverse a graph using Depth First Search (DFS)?

In a Depth First Search (DFS) traversal of a graph, you traverse the vertices depth wise rather than breadth wise. You start by traversing from any vertex say currentVertex - pick any one of it's adjacent vertex and keep traversing adjacent vertices until the farthest vertex is reached. Then you move back to the starting vertex and repeat the same for another adjecent vertex. You repeat this process until all the vertices are traversed.