Question 6-4

Consider the following method, which finds and removes some duplicated nonzero number in the parameter array, returning true if it found one.

public static boolean removeDuplicate(char[] arr) {
    int i, j;
outer:
    for(i = 0; i < arr.length; i++) {
        for(int j = i + 1; j < arr.length; j++) {
            if(arr[i] != 0 && arr[i] == arr[j]) break outer;
        }
    }
    if(i == arr.length { // no duplicate found
        return false;
    } else { // we found a duplicate; shift elements down over j
        for(int k = j + 1; k < arr.length; k++) {
            arr[k - 1] = arr[k];
        }
        arr[arr.length - 1] = 0;
        return true;
    }
}

Let n represent the length of arr. In terms of n, how much time does the above method take? Use Big-O notation to express your answer, and provide the tightest bound that you can.

Solution

O(n²)

Back to Review for Quiz 6