Home CPSC 340

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

When you're finished, email your answers to ifinlay@umw.edu.

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