Quiz 13 Solution

Determine the WORST-CASE complexity of the following code fragments in
terms of 'n'.  Do this by counting the number of comparisons it
performs, and determining its Big-Oh complexity. Assume the initial
value of n is less than 0.  [each part is worth 2 marks]

a)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("hello");
    }
}

# of comparisons:  n^2
Big-Oh:    O (n^2)

b)
for (int i = 0; i < n; i++) {
    if (i < m) {
        break;
    }

    for (int j = 0; j < n; j++) {
        System.out.println("hello");
    }
}

# of comparisons:  n + n^2
Big-Oh: O (n^2)

c)  NOTE: This part will not be marked.  This question is more
    complex than what we had intended.  The quiz will be marked
    out of 8 instead of 10.
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        n--;
    }
}

# of comparisons: 2 + n (this is not correct)
Big-Oh: O (n)

d)
int b = n;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        n--;
    }
    n = b;
}

# of comparisons:  n * 1/2 n
Big-Oh:  O(n^2)

e)
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            int counter = 0;
            while (counter < n){
                System.out.println("hello");
                counter++;
            }
        }
    }
}

# of comparisons:  n ^4
Big-Oh:  O(n^4)