How to determine your programs runtime?

Question

I have to write a divide-and-conquer program to solve the following problem. Let A[1..n] and B[1..n] be two arrays of distinct integers, each sorted in an increasing order.Find the nth smallest of the 2n combined elements. I can not merge the two arrays. My program must be in O(log n) time.

I have written my program but have no clue how to determine if it meets the requirement of the run time.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;

public class main {

public static void main(String[] args) {

    // this section of code will require user input to have the value of n to be set
    Scanner sc = new Scanner(System.in);
    System.out.print(("What number would you like to set n equal to : "));
    int value = sc.nextInt();

    // this section of code set the two array only to hold the value of n
    Random rand = new Random();
    ArrayList<Integer> setA = new ArrayList<Integer>();
    for (int i = 0; i < value; i++) {
        int picks = rand.nextInt(1000);
        setA.add(picks);
    }
    Collections.sort(setA);
    System.out.println("A1: "+ setA);


    ArrayList<Integer> setX = new ArrayList<Integer>();
    for (int k = 0; k < value; k++) {
        int picks = rand.nextInt(1000);
        setX.add(picks);
    }
    Collections.sort(setX);
    System.out.println("A2: "+ setX);

    ArrayList<Integer> afinal = new ArrayList<Integer>();

    int r = 0;
    int f = 0;
    int q = 0;
    while(afinal.size()!=  value) {
        if(setA.get(r) < setX.get(f)) {
            q = setA.get(r);
            afinal.add(q);
            r++;
        }else {
            q = setX.get(f);
            afinal.add(q);
            f++;
        }
    
    }
    System.out.println("");
    System.out.println(afinal);
    int w = value - 1;
    int ans = afinal.get(w);
    System.out.println("");
    System.out.println("The nth smallest integer is "+ ans);
}
}

Time it...? https://stackoverflow.com/questions/2572868/how-to-time-java-program-execution-speed — marsnebulasoup, Oct 16 '20 at 23:37
Try this: https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm — Jimmy Xin, Oct 17 '20 at 01:59

score 0 · Answer 1 · answered Oct 17 '20 at 00:08

You can calculate runtime with System.currentTimeMillis().

What we want to do is get the current time before the program runs, then get the time after the program runs. We then handle the two times accordingly.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;

public class main {

public static void main(String[] args) {
    long before = System.currentTimeMillis();

    // this section of code will require user input to have the value of n to be set
    Scanner sc = new Scanner(System.in);
    System.out.print(("What number would you like to set n equal to : "));
    int value = sc.nextInt();

    // this section of code set the two array only to hold the value of n
    Random rand = new Random();
    ArrayList<Integer> setA = new ArrayList<Integer>();
    for (int i = 0; i < value; i++) {
        int picks = rand.nextInt(1000);
        setA.add(picks);
    }
    Collections.sort(setA);
    System.out.println("A1: "+ setA);


    ArrayList<Integer> setX = new ArrayList<Integer>();
    for (int k = 0; k < value; k++) {
        int picks = rand.nextInt(1000);
        setX.add(picks);
    }
    Collections.sort(setX);
    System.out.println("A2: "+ setX);

    ArrayList<Integer> afinal = new ArrayList<Integer>();

    int r = 0;
    int f = 0;
    int q = 0;
    while(afinal.size()!=  value) {
        if(setA.get(r) < setX.get(f)) {
            q = setA.get(r);
            afinal.add(q);
            r++;
        }else {
            q = setX.get(f);
            afinal.add(q);
            f++;
        }
    
    }
    System.out.println("");
    System.out.println(afinal);
    int w = value - 1;
    int ans = afinal.get(w);
    System.out.println("");
    System.out.println("The nth smallest integer is "+ ans);
    long after = System.currentTimeMillis();
}
}

In the example above, we've got the two times. Now what do we do?

We can subtract them to get the difference in times (by milliseconds).

Like so:

long ellapsedMilliseconds = after-before;

If you want to get the elapsed time in seconds, divided ellapsedMilliseconds by 100.

So the final code should be;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Random;
import java.util.Scanner;

public class main {

public static void main(String[] args) {
    long before = System.currentTimeMillis();

    // this section of code will require user input to have the value of n to be set
    Scanner sc = new Scanner(System.in);
    System.out.print(("What number would you like to set n equal to : "));
    int value = sc.nextInt();

    // this section of code set the two array only to hold the value of n
    Random rand = new Random();
    ArrayList<Integer> setA = new ArrayList<Integer>();
    for (int i = 0; i < value; i++) {
        int picks = rand.nextInt(1000);
        setA.add(picks);
    }
    Collections.sort(setA);
    System.out.println("A1: "+ setA);


    ArrayList<Integer> setX = new ArrayList<Integer>();
    for (int k = 0; k < value; k++) {
        int picks = rand.nextInt(1000);
        setX.add(picks);
    }
    Collections.sort(setX);
    System.out.println("A2: "+ setX);

    ArrayList<Integer> afinal = new ArrayList<Integer>();

    int r = 0;
    int f = 0;
    int q = 0;
    while(afinal.size()!=  value) {
        if(setA.get(r) < setX.get(f)) {
            q = setA.get(r);
            afinal.add(q);
            r++;
        }else {
            q = setX.get(f);
            afinal.add(q);
            f++;
        }
    
    }
    System.out.println("");
    System.out.println(afinal);
    int w = value - 1;
    int ans = afinal.get(w);
    System.out.println("");
    System.out.println("The nth smallest integer is "+ ans);
    long after = System.currentTimeMillis();
    long ellapsedMilliseconds = after-before;
    System.out.println("Execution time: "+elapsedMilliseconds);
}
}

How to determine your programs runtime?

1 Answers1