Review 0: Big O
printable version
R0: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]
Problem R0.1
Write the following Big-O bounds in order, from smallest to largest.
O(1), O((log n)²), O(n0.0001), O(n log n), O(n √n), O(n²), O(1.01n)
Problem 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;
}
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).
Problem 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) { | b.int pow(int m, int n) { |
| a. | O(n) |
| b. | O(log n) |
Problem 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;
}
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²).
Problem 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;
}
Problem 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;
}
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).
Problem 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;
}
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).
Problem 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;
}
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).
Problem 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;
}
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).
Problem 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;
}
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.