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:


// 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;
}


// 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;
    }
}


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;
}


// 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;
}


// 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.