a(x) = 8x + 3 = ϴ(x)
b(x) = 12x + x^{2} + 64
c(x) = 2log(x) + x
d(x) = log(x) + 2
e(x) = sqrt(2x)
Solution: a(x) = 8x + 3 = ϴ(x) // already given b(x) = 12x + x^2 + 64 = ϴ(x^2) c(x) = 2log(x) + x = ϴ(x) d(x) = log(x) + 2 = ϴ(log(x)) e(x) = sqrt(2x) = sqrt(2) * sqrt(x) = ϴ(sqrt(x))
count()
function is called when the following code fragment runs, in terms of
the variable n
.
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k < j; k++)
count();
Include a short explanation of your answer by explaining how many times each loop iterates.
Solution: The inner two for loops are essentially the same as in Selection sort (upper triangle of a square with side n), so Theta(n^2); the outer loop runs n times, so Theta(n^2) * n = Theta(n^3).
count()
function is called when the following code fragment runs, in terms of
the variable n
.
for (int i = n; i > 0; i /= 2)
for (int j = 0; j < n; j++)
for (int k = 0; k < 1000; k++)
count();
Include a short explanation of your answer by explaining how many times each loop iterates.
Solution: The outer loop divides i in half each time, and you can divide a number in half at most Theta( log(n) ) times; The second loop runs n times; The inner loop runs 1000 times; So Theta( log(n) ) * n * 1000 = Theta( n * log(n) )
public static void insertion(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1])
swap(arr, j, j - 1);
// show array here
}
}
}
Execute the algorithm on the following input:
+-------------------+ | 3 | 5 | 8 | 2 | 1 | +-------------------+
Solution: 3 5 8 2 1 original array 3 < 5 < 8 so no swapping 3 5 8 * 2 1 section to left of * is sorted, now inserting 2 into sorted part 3 5 2 8 * 1 swap 2 and 8
3 2 5 8 * 1 swap 2 and 5
2 3 5 8 * 1 swap 2 and 3; 2 is in proper place, now will insert 1
2 3 5 1 8 * etc.
2 3 1 5 8 *
2 1 3 5 8 *
1 2 3 5 8 * done!
public static void selection(int[] arr) {
int k;
for (int i = 0; i < arr.length; i++) {
k = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[k])
k = j;
}
swap(arr, i, k);
// show array here
}
}
Execute the algorithm on the following input:
+-------------------+ | 9 | 6 | 4 | 2 | 3 | +-------------------+
Solution: 9 6 4 2 3 original array
2 * 6 4 9 3 find min 2, swap with 9
2 3 * 4 9 6 find min 3, swap with 6
2 3 4 * 9 6 find min 4, swap with 4 (ha!)
2 3 4 6 * 9 find min 6, swap with 9
2 3 4 6 9 * find min 9, swap with 9 (ha!
2 3 4 6 9 done!
+-------------------------------+ | 9 | 5 | 3 | 2 | 1 | 8 | 7 | 4 | +-------------------------------+ Solution: [9, 5, 3, 2, 1, 8, 7, 4] (input array) - - - - - - - - (subproblems of size 1) [5, 9, (subproblems of size 2) ---- 2, 3, ---- 1, 8, ---- 4, 7] ---- [2, 3, 5, 9, (subproblems of size 4) ---------- 1, 4, 7, 8] ---------- [1, 2, 3, 4, 5, 7, 8, 9] done! ----------------------