Question

Question: I am using three different ways to execute this program. I am a bit confused on the time complexity for each one. Can someone explain the time complexity for each function in relation to the nanoseconds.

import java.util.HashMap;
import java.util.Map;
public class twosums {
  
   public static void main(String args[]) {
      
       int[] numbers = new int[] {2,3,9,4,8};;
       int target = 10;
      
       long nano_begin1 = System.nanoTime();
       int[] result1 = twoSums(numbers,target);
       long nano_end1 = System.nanoTime();
      
       long nano_begin2 = System.nanoTime();
       int[] result2 = twoSums2(numbers,target);
       long nano_end2 = System.nanoTime();
      
       long nano_begin3 = System.nanoTime();
       int[] result3 = brutForce(numbers,target);
       long nano_end3 = System.nanoTime();
      
       System.out.println("Two Sums using one pass: " + result1[0] + " " + result1[1] + " -> "+ (nano_end1 - nano_begin1));
   System.out.println("Two Sums using two pass: " + result2[0] + " " + result2[1] + " -> "+ (nano_end2 - nano_begin2));
   System.out.println("Brut Force: " + result3[0] + " " + result3[1] + " -> " + (nano_end3 - nano_begin3));
      
   }
  
   public static int [] brutForce(int[] nums, int target) {
      
      
       for(int i = 0; i < nums.length; i++) {
          
           for(int j = i + 1; j < nums.length; j++) {
              
               if(nums[j] == target - nums[i]){
                  
                   return new int [] {i,j};
               }
           }
          
       }
      
       throw new IllegalArgumentException("No two sums add up to target number");
      
   }
  
   public static int[] twoSums(int[] nums, int target) {
      
       Map <Integer, Integer> funguy = new HashMap<>();
       for(int i = 0; i < nums.length; i++) {
          
           funguy.put(nums[i], i);
       }
      
       for(int i = 0; i < nums.length; i++) {
          
          
           int complement = 0;
           complement = target - nums[i];
      
           if(funguy.containsKey(complement)) {
              
               return new int[] {i, funguy.get(complement)};
           }
       }
      
       throw new IllegalArgumentException("No two numbers add up to target number!");
      
   }
  
   public static int[] twoSums2(int[] nums, int target) {
      
       Map <Integer, Integer> funguy = new HashMap<>();
       for(int i = 0; i < nums.length; i++) {
          
           int complement = 0;
           complement = target - nums[i];
          
          
           if(funguy.containsKey(complement)) {
              
               return new int[] { funguy.get(complement), i};
           }
          
           funguy.put(nums[i], i);

       }
      
       throw new IllegalArgumentException("No two numbers add up to target number!");
  
  
   }
  
}

Answer 1

In brute force approach , it is checking all possible pairs in array nums[], whose sum equal to target.
In worst case
let nums.length = n
for(int i = 0; i < nums.length; i++) { ---------runs n times
        
           for(int j = i + 1; j < nums.length; j++) {
            
               if(nums[j] == target - nums[i]){
                
                   return new int [] {i,j};
               }
           }

for i=0 inner loop runs (n-1) times
for i=1 inner loop runs (n-2) times
for i=2 inner loop runs (n-3) times
and so on......

Total run = (n-1) + (n-2) + (n-3) + ........+ 2 + 1
T(n) = n*(n-1)/2 = O(n^2)

twoSums(int[] nums, int target)
A HashMap created which takes n times
and for searching it also take n times
Total run = 2*n

twoSums2(int[] nums, int target)
A HashMap creation and searching both done in single for Loop
Total run = n

order of runtime
Brute Force > twoSums > twoSums2