Question

Question: I am using three different ways to execute this program. I am a bit confused...

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!");
  
  
   }
  
}

Homework Answers

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

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
PP 8.2 Modify the program from PP 8.1 so that it works for numbers in the...
PP 8.2 Modify the program from PP 8.1 so that it works for numbers in the range between −25 and 25 THIS IS MY CODE! please edit this...Thank you import java.util.Scanner; public class Array { public static void main (String[] args) { Scanner scan = new Scanner (System.in); int[] integs = new int[51]; System.out.println("Enter integers 0-50 [enter -1 to quit]: "); int nums = scan.nextInt(); while (nums != -1 && nums>=0 && nums<=50) { integs[nums]++; nums = scan.nextInt(); } for...
I need to get the Min and Max value of an array when a user inputs...
I need to get the Min and Max value of an array when a user inputs values into the array. problem is, my Max value is right but my min value is ALWAYS 0. how do i fix this? any help please!!! _________________________________________________________________________________________________ import java.util.Scanner; public class ArrayMenu{ static int count; static Scanner kb = new Scanner(System.in);             public static void main(){ int item=0; int[] numArray=new int[100]; count=0;       while (item !=8){ menu(); item = kb.nextInt();...
I have the following program which returns F(n) for the fibonacci sequence both recursively and iteratively:...
I have the following program which returns F(n) for the fibonacci sequence both recursively and iteratively: public class Fibonacci { //Recursive method public int fibRecursive(int n) { //If n is in the 0th or 1st place return n if (n <= 1) return n; return fibRecursive(n - 1) + fibRecursive(n - 2); } //Iterative method public int fibIterative(int n) { if (n <= 1) return n; int fib = 1, prevFib = 1; for (int i = 2; i <...
Solve Project 2 using a TreeMap. You can display the words in key sequence without performing...
Solve Project 2 using a TreeMap. You can display the words in key sequence without performing a sort. Java Project 2: Use a HashMap to store the frequency counts for all the words in a large text document. When you are done, display the contents of this HashMap. Next, create a set view of the Map and store its contents in an array. Then sort the array based on key value and display it. Finally, sort the array in decreasing...
Create the ArrayList program example in listing 13.1, Battlepoint. Describe the code (in your WORD document)...
Create the ArrayList program example in listing 13.1, Battlepoint. Describe the code (in your WORD document) in the 'if' statement if (targets.indexOf(shot) > -1) { ADD a NEW ArrayList of points called 'misses' ADD code to add a point to the 'misses' list on a miss (if a SHOT does NOT hit a TARGET) ADD code to place an 'M' in the final output map for all shots that were MISSES. ADD code to place an H on the target...
1) Consider the following Java program. Which statement updates the appearance of a button? import java.awt.event.*;...
1) Consider the following Java program. Which statement updates the appearance of a button? import java.awt.event.*; import javax.swing.*; public class Clicker extends JFrame implements ActionListener {     int count;     JButton button;     Clicker() {         super("Click Me");         button = new JButton(String.valueOf(count));         add(button);         button.addActionListener(this);         setSize(200,100);         setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);         setVisible(true);     }     public void actionPerformed(ActionEvent e) {         count++;         button.setText(String.valueOf(count));     }     public static void main(String[] args) { new Clicker(); } } a. add(button);...
Complete the following program. This program should do the following: 1. Creates a random integer in...
Complete the following program. This program should do the following: 1. Creates a random integer in the range 10 to 15 for variable: allThreads, to create a number of threads. 2. Creates a random integer for the size of an ArrayList: size. 3. Each thread obtains a smallest number of a segment of the array. To give qual sized segment to each thread we make the size of the array divisible by the number of threads: while(size%allThreads != 0)size++ 4....
Hello, I am trying to create a Java program that reads a .txt file and outputs...
Hello, I am trying to create a Java program that reads a .txt file and outputs how many times the word "and" is used. I attempted modifying a code I had previously used for counting the total number of tokens, but now it is saying there is an input mismatch. Please help! My code is below: import java.util.*; import java.io.*; public class Hamlet2 { public static void main(String[] args) throws FileNotFoundException { File file = new File("hamlet.txt"); Scanner fileRead =...
Do a theta analysis and count the number of computations it performed in each function/method of...
Do a theta analysis and count the number of computations it performed in each function/method of the following code: import java.io.*; import java.util.Scanner; class sort { int a[]; int n; long endTime ; long totalTime; long startTime; static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); public sort(int nn) // Constructor { a = new int[nn]; n = nn; endTime= 0; totalTime =0; startTime =0; } public static void main(String args[]) throws IOException { System.out.print("\nEnter number of students: "); int nn =...
If you cant answer this please dont waste my question. thank you. This cryptographic program run...
If you cant answer this please dont waste my question. thank you. This cryptographic program run and produce text screen output. You are to create a GUI that uses the program. Your program (GUI) must allow a user to input of a message to be coded. It must also have an area to show the plaintext, the ciphertext, and the decrypted text. If required by your choice of cryptographic method, the user should have an area to input a key....
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT