Definition: Linear search (also as known as sequential search) is the process of finding a value by searching through every element till we find the value that we want.

Linear Search Implementation in Java

public int linearSearch(int a[], int target){

//returns the index of the target 
for(int x=0; x<a.length; x++){
if(a[x] == target)
      return x;
 }
 
 //returns -1 if the element is not found
 return -1;
}

Time Complexity: The time complexity of this prorgram is O(n) because it will take a very short time to find the first element but then finding the next element will take longer and so on. The time it takes to find each element will increase linearly which is why the time complexity is O(n).

Best Case, Average Case, and Worst Case

Best Case: You found the first element

 Big O Notation: O(1)

Average Case: You found the middle element

 Big O Notation: O(n), even though it is O(n/2) but remember we will drop the constant which is 1/2

Worst Case: You found the last element or element is not found

 Big O Notation: O(log n)

Definition: Binary search (also as known as half-interval search) is used to find a specific value within an array by cutting half of an array.

Binary Search Implementation in Java

public static int binarySearch (int[] arr, int from, int to, int target) {

if (from > to) {
  
   return -1; //val not found 

}
  
int mid = (from + to)/2;

if (arr[mid] == target){

   return mid;

}else if (target > arr[mid]){
   
   return binSearch(arr,mid+1,to,target);

}else{

   return binSearch(arr,from,mid-1,target);

      }

}

Time Complexity: The time complexity of this prorgram is O(log n) since we are dividing the length of the line and getting rid of the half that surely does not contain the value. We keep on doing this until our line is just empty. A line with a length of 8 will cut the line at most 3 times since log 8 is 3. Remember our base of the log is 2 so 2^3 is 8. For more information about the log n runtime click here.

Best Case and Worst Case

Best Case: We found the element by first comparison

 Big O Notation: O(1)

Worst Case: We found the element by last comparison or element was not found at all

Big O Notation: O(n)

Defintion: Insertion sort is a sorting algorithm that builds an element one item at a time.

Insertion Sort Implementation in Java

public static void insertion2(int[] a){ 

   int n = a.length;
   for (int i = 1; i < n; i++){
   
       for (int j = i; j > 0; j--){
       
          if(a[j-1] > a[j]){
          
           int temp = a[j-1];  
           a[j-1] = a[j];  
           a[j] = temp;
           
          }else {
          
            break;
            
          }
            
        } 
        
    }
    
}

Time Complexity: The time complexity of this prorgram is O(n^2) since it is a nested for loop where the input, n, is our array.

Best Case and Worst Case

Best Case: Best case applies to an array that is already sorted from the least to the greatest. In this case, we will traverse through the array which is why the runtime is O(n).

Big O Notation: O(n)

Worst Case: Worst case applies to an array that goes from the greatest value to the least value.

Big O Notation: O(n^2)

Definition: Selection sort is a sorting algorithm that sorts an array by repeatedly finding the minimum value and placing it to the beginning of the array until the array is sorted.

Selection Sort Implementation in Java

public static void sort(int[] a) { 

        int n = a.length;
      for (int i = 0; i < n; i++) {
      
           int min = i;
          for (int j = i+1; j < n; j++) {
          
              if (a[j] < a[min]) 
                    min = j;
                    
          }
          
         int tmp = a[i]; 
         a[i] = a[min]; 
         a[min]= tmp;
         
      } 
      
}

Time Complexity: The time complexity of this prorgram is O(n^2) since it is a nested for loop where the input, n, is our array.

Best Case and Worst Case

Best Case: Best case applies to an array that is already sorted from the least to the greatest. We still go through each element for every array run which is why the runtime is still O(n^2).

Big O Notation: O(n^2)

Worst Case: Worst case applies to an array that goes from the greatest value to the least value.

Big O Notation: O(n^2)

Definition: Merge sort is a storting algorithm which consists of dividing the elements and bringing back the elments to a sorted group of elements.

Selection Sort Implementation in Java

public static void sort (int[] a, int lo, int hi){
   
   int n = hi - lo;   
  
    if ( n <= 1 ) 
        return;  
 
  int middle = lo + n/2;
    
  sort(a, lo, middle);   
  sort(a, middle, hi);   
  merge(a, lo, middle, hi); 
   
}
     
public static void merge (int[] a, int lo, int mid, int hi){
    
     int i =  lo, j = mid, n = hi - lo;
     int[] aux = new aux[n];   
     
     for (int k = 0; k < n; k++) {     
       
        if (i == mid) 
            aux[k] = a[j++];   
        else if (j == hi) 
            aux[k] = a[i++];     
        else if (a[j] < a[i]) 
            aux[k] = a[j++];
        else 
            aux[k] = a[i++];
        
        }
        

Time Complexity: The time complexity of this prorgram is O(nlog n) since n items are iterated log n times.

Best Case and Worst Case

Best Case: Even if the array is sorted, it will still divide and conqueror.

Big O Notation: O(nlog n)

Worst Case: It will apply to an arrary that goes from the greatest to the least which consists of divide and conqueror.

Big O Notation: O(nlog n)