Home CPSC 340

Lab 7: Big-O Exercise

 

Due: October 9


 

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.

Copyright © 2020 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.