Review 0: Big O: Questions

R0.1.

Write the following Big-O bounds in order, from smallest to largest.

O(n²), O(1.01n), O((log n)²), O(n √n), O(n log n), O(n0.0001), O(1)
R0.2.

Using big-O notation in terms of the parameter n, how much time does the following method take? Give the tightest and simplest bound possible, and justify your answer.

public static int mystery(int n) {
    int count = 0;
    int cur = 1;
    while (cur < n) {
        count++;
        cur = cur * 2;
    }
    return cur;
}
R0.3.

Each of the below methods determine mn without using Math.pow. Using big-O notation in terms of n, how much time does each take? Give the tightest and simplest bounds possible, and justify your answers.

a.
int pow(int m, int n) {
    int ret = 1;
    for (int i = 0; i < n; i++) {
        ret *= m;
    }
    return ret;
} 		b.
int pow(int m, int n) {
    int ret = 1;
    int k = m;
    int i = n;
    while (i > 0) {
        if (i % 2 == 1) ret *= k;
        k *= k;
        i /= 2;
    }
    return ret;
}
R0.4.

Using big-O notation in terms of the parameter n, how much time does the below method take? Give the tightest and simplest bound possible, and justify your answer.

public static int mystery(int n) {
    int i = 1;
    int j = 0;
    while (i < n) {
        j++;
        if (j == i) {
            i++;
            j = 0;
        }
    }
    return j;
}
R0.5.

The below method finds and removes all duplicated numbers in the parameter array. Note that it has three loops.

Using big-O notation in terms of n, the length of arr, how much time does this method take? Give the tightest and simplest bound possible, and justify your answer.

public static int removeDuplicates(char[] arr) {
    int len = arr.length;
    int i = 0;           // index of current item to find
    while (i < len) {
        int j;           // will be index of duplicate of arr[i]
        for (j = i + 1; j < len; j++) {
            if (arr[i] == arr[j]) break;
        }
        if (j == len) {   // no duplicate of arr[i] found; go to next i
            i++;
        } else {         // duplicate found; shift array over arr[j]
            for (int k = j + 1; k < len; k++) {
                arr[k - 1] = arr[k];
            }
            len--;
            arr[len] = 0;
        }
    }
    return len;
}
R0.6.

Using big-O notation in terms of its parameter n, what is the running time of the below method? Give the tightest and simplest bound possible, and justify your answer.

public static int compute(int n) {
    int total = 0;
    for (int i = 1; i < n; i++) {
        int k = 1;
        while (k < i) { k = k + k;          }
        while (k > 1) { k /= 2;    total++; }
    }
    return total;
}
R0.7.

The following method finds the smallest factor above 1 for a given number n, without using any division or multiplication. (A factor for a number n is an integer that divides into n exactly. For example, the factors of 45 are 1, 3, 5, 9, 15, and 45.)

Using big-O notation in terms of its parameter n, how much time does this method take? Give the tightest and simplest bound possible, and justify your answer.

public static int findFactor(int n) {
    int i = 1;
    int j = n - 1;
    int p = j; // invariant: p = i * j
    while (p != n && i < j) {
        i++; p += j;
        while (p > n) { j--; p -= i; }
    }
    return p == n ? i : n;
}
R0.8.

Using big-O notation in terms of its parameter n, what is the running time of the below method? Give the tightest and simplest bound possible, and justify your answer.

public static int mystery(int n) {
    int total = 0;
    for (int i = 1; i < n; i *= 2) {
        for (int j = i; j < 2 * i; j++) {
            total += j;
        }
    }
    return total;
}
R0.9.

The following method determines whether the parameter array of booleans contains at least two true values. Using big-O notation in terms of n, the length of the parameter array, how much time does this method take? Give the tightest and simplest bound possible, and justify your answer.

public static int findTruePair(boolean[] flags) {
    int n = flags.length;
    for (int i = 0; i < n; i++) {
        if (flags[i]) {
            for (int j = i + 1; j < n; j++) {
                if (flags[j]) return true;
            }
        }
    }
    return false;
}
R0.10.

We can define the trailing zeroes of an integer k as the zeroes following the last 1 in k's binary representation; for example, the number 20 (represented in binary as 10100) has two trailing zeroes. The below method returns the total number of trailing zeroes for all integers from 1 to its parameter n; given 10, it returns 0 + 1 + 0 + 2 + 0 + 1 + 0 + 3 + 0 + 1 = 8.

Using big-O notation in terms of its parameter n, what is the running time of the below method? Give the tightest and simplest bound you can, and justify your answer.

public static int countTrailingZeroes(int n) {
    int total = 0;
    for (int num = 1; num <= n; num++) {
        for (int div = 2; num % div == 0; div *= 2) {
            total++;
        }
    }
    return total;
}

Review 0: Big O: Solutions

R0.1.

O(1), O((log n)²), O(n0.0001), O(n log n), O(n √n), O(n²), O(1.01n)

R0.2.

It takes O(log n) time. Since cur doubles with each iteration of the loop, after going through the loop k times, cur will be 2k. After going through the loop log2 n times, cur will be 2log2 n, or n, and we will stop. Thus, there are O(log n) iterations of the loop; since each iteration takes O(1) time, the total time consumed is O(log n).

R0.3.
a.O(n)
b.O(log n)
R0.4.

It takes O(n²) time. We go through the loop once when i is 0, twice when i is 1, three times when i is 2, three times when i is 2, and so on. We stop by the time i reaches n; so the question is: What is 1 + 2 + 3 + … + n? This summation is n (n + 1) / 2 = (1/2) n² + (1/2) n = O(n²).

R0.5.
O(n²)
R0.6.

O(n log n): For each i value, each inner loop has approximately log2 i iterations — the first one starting at 1 and doubling until we reach i, and the second one halving until we reach 1 again. Thus, the total time per iteration of the outer loop is O(log i + log i) = O(2 log i) = O(log i) = O(log n). (The last step comes from the fact that i ≤ n.) The outer loop has n iterations, so the total time is O(n log n).

R0.7.

An answer of O(n √n) would be partially acceptable. The reasoning: As we go through the loop, j always decreases to a number less than n / i, and so once i reaches √n, n / i will be less than that, and the method stops. Thus, there are at most √n iterations of the outer loop. For each iteration, j may have to decrease significantly, but it won't decrease for more than n iterations, so O(n √n) is a valid answer.

It is possible, however, to derive a better bound by observing that the total number of iterations of inner loop, across the entire method execution, will be less than n, since j starts at n − 1, decrements each time through the inner loop, and stops once it reaches √n. Thus, the total time spent on the inner loop over the entire execution is O(n), and the total time spent on the outer loop (but not including time for the inner loop) is O(√n); thus, the total time overall is O(√n + n) = O(n).

R0.8.

A first-cut solution, which would be partially acceptable, would be O(n log n): The reasoning would be that the outer loop has log2 n iterations since i starts at 1 and doubles with each iteration until it reaches n, and log2 n doublings will accomplish this, while the inner loop has at most 2 n iterations, since j starts at i, which is at least 1, and stops at 2 i, which is less than 2 n since i is less than n. Thus we have O((log2 n) 2 n) = O(n log n) time.

An answer of O(n) is also possible. The reasoning is this: The inner loop will execute only once the first time through the outer loop (when i is 1), twice on the second outer iteration (when i is 2), four times on the third outer iteration (when i is 4), and so on. Thus, the total number of iterations of the inner loop, across all iterations of the outer loop, is 1 + 2 + 4 + 8 + … + n = 2 n − 1, and so the total time spent on the inner loop is O(n). If we ignore the inner loop, the total time spent on the outer loop is O(log n), so the total time overall is O(n + log n) = O(n).

R0.9.

O(n). If flags contains no true values, then the inner loop will never execute, so every iteration of the outer loop takes O(1) time, for a total of O(n) time. If flags contains one true value, then the inner loop will be reached only once, adding an additional O(n) to the above, for a total still of O(n). And if flags contains two or more true values, then the inner loop will still be reached only once (since the one time the inner loop is executed, the method will return), for a total of O(n) time. So in any of these cases, the amount of time is O(n).

R0.10.

A partially acceptable answer is O(n log n). For this answer, you have only to observe that there are precisely n iterations of the outer loop, and for each iteration, we can have a maximum of log2 n iterations of the inner loop.

However, O(n) is a better solution. Here, we observe that for half of the numbers from 1 to n, there are no iterations of the inner loop. Half of the numbers see a first iteration of this inner loop, while a quarter see a second iteration, and an eight see a third iteration, and so on. Thus, the total number of iterations of this inner loop is at most n/2 + n/4 + n/8 + … = n.