Lab 4: Big-O Exercise

Objective

To come up with Big-O complexities for methods.

Task

For this lab you will determine the Big-O of several methods. For each one, provide the Big-O complexity, along with a short justification. Also, be sure to indicate what "N" refers to.

You can determine the complexities by counting steps, using reasoning skills, or by running the code in order to understand how the methods are working.

Details

The methods are the following:

1. 
   // check if a particular number is found in an array
   public static int exists(int[] array, int number) {
       for (int i = 0; i < array.length; i++) {
           if (array[i] == number) {
               return true;
           }   
       }   
   
       return false;
   }   
   

2. 
   // compare two throws in Rock-Paper-Scissors to determine a winner
   public static Result compareThrows(Throw p1, Throw p2) {
       if (p1 == Throw.ROCK) {
           if (p2 == Throw.ROCK) return Result.DRAW;
           if (p2 == Throw.PAPER) return Result.PLAYER2;
           if (p2 == Throw.SCISSORS) return Result.PLAYER1;
       } else if (p1 == Throw.PAPER) {
           if (p2 == Throw.ROCK) return Result.PLAYER1;
           if (p2 == Throw.PAPER) return Result.DRAW;
           if (p2 == Throw.SCISSORS) return Result.PLAYER1;
       } else {
           if (p2 == Throw.ROCK) return Result.PLAYER2;
           if (p2 == Throw.PAPER) return Result.PLAYER1;
           if (p2 == Throw.SCISSORS) return Result.DRAW;
       }
   }   
   

3. 
   public static int mode(int[] array) {
       int mode = 0;
       int modeCount = 0;
   
       for (int i = 0; i < array.length; i++) {
           // see how many times this item appears total
           int count = 0;
           for (int j = 0; j < array.length; j++) {
               if (array[i] == array[j]) {
                   count++;
               }
           }
   
           // keep track of what has appeared most
           if (count > modeCount) {
               mode = array[i];
               modeCount = count;
           }
       }
   
       return mode;
   }   
   

4. 
   // check if a number is prime or not
   public static boolean isPrime(int n) {
       int divisor = 2;
       while (divisor <= (n / 2)) {
           if (n % divisor == 0) {
               return false;
           }
           divisor++;
       }
   
       return true;
   }
   

5. 
   // generate all numeric codes of a given number of digits
   public static void genCodes(int n) {
       int[] code = new int[n];
   
       boolean done = false;
       while (!done) {
           // print this code
           for (int i = n-1; i >= 0; i--) {
               System.out.print(code[i]);
           }
           System.out.print("\n");
   
           // move to the next one
           int slot = 0;
           while (true) {
               code[slot]++;
               if (code[slot] != 10) {
                   break;
               } else {
                   code[slot] = 0;
                   slot++;
   
                   // if slots overfills, we are done
                   if (slot >= n) {
                       done = true;
                       break;
                   }
               }
           }
       }
   }   
   

Submitting

You should enter your answers into the Canvas assignment for this lab, either as an attachment or as text.