This document contains solutions to homework problems involving algorithm analysis. Problem 1 analyzes the runtime of a function and shows it is O(n^2) and Ω(n). Problem 2 analyzes another function and shows it is O(n^2) and Ω(n). Problem 3 derives the complexity of a sequence of expressions from Θ(√log n) to O(2^n). Problem 4 analyzes two algorithms, one taking Θ(n log n) time and the other taking Θ(n^3) time. Problem 5 presents an algorithm to count pairs in a list and analyzes it as Θ(n log n). Problem 6 presents three parts: an O(n
This document contains solutions to homework problems involving algorithm analysis. Problem 1 analyzes the runtime of a function and shows it is O(n^2) and Ω(n). Problem 2 analyzes another function and shows it is O(n^2) and Ω(n). Problem 3 derives the complexity of a sequence of expressions from Θ(√log n) to O(2^n). Problem 4 analyzes two algorithms, one taking Θ(n log n) time and the other taking Θ(n^3) time. Problem 5 presents an algorithm to count pairs in a list and analyzes it as Θ(n log n). Problem 6 presents three parts: an O(n
This document contains solutions to homework problems involving algorithm analysis. Problem 1 analyzes the runtime of a function and shows it is O(n^2) and Ω(n). Problem 2 analyzes another function and shows it is O(n^2) and Ω(n). Problem 3 derives the complexity of a sequence of expressions from Θ(√log n) to O(2^n). Problem 4 analyzes two algorithms, one taking Θ(n log n) time and the other taking Θ(n^3) time. Problem 5 presents an algorithm to count pairs in a list and analyzes it as Θ(n log n). Problem 6 presents three parts: an O(n
This document contains solutions to homework problems involving algorithm analysis. Problem 1 analyzes the runtime of a function and shows it is O(n^2) and Ω(n). Problem 2 analyzes another function and shows it is O(n^2) and Ω(n). Problem 3 derives the complexity of a sequence of expressions from Θ(√log n) to O(2^n). Problem 4 analyzes two algorithms, one taking Θ(n log n) time and the other taking Θ(n^3) time. Problem 5 presents an algorithm to count pairs in a list and analyzes it as Θ(n log n). Problem 6 presents three parts: an O(n
Sriram Pemmaraju CS:3330 (Pai and Pemmaraju ): Homework 2 Solutions
Problem 1 (a) Pick c = 37 and n0 = 1. We know that
2n2 + 15n + 20 ≤ 2n2 + 15n2 + 20n2 for all n ≥ 1.
From this we see that 2n2 + 15n + 20 ≤ 37n2 for all n ≥ 1. This shows that f = O(n2 ).
(b) Pick c = 2 and n0 = 1. We know that
2n2 + 15n + 20 ≥ 2n for all n ≥ 1.
This shows that f = Ω(n).
Problem 2 We know that log2 n ≤ n for all n ≥ 1. Therefore, 7n log2 n ≤ 7n2 for all n ≥ 1. This establishes that f = O(n2 ). We know that log2 n ≥ 1 for all n ≥ 2. Therefore, 7n log2 n ≥ 7n for all n ≥ 2. This establishes that f = Ω(n).
Problem 3 √ log2 n 1) Since 2log2 n = n, 2 < 2log2 n = n for all n ≥ 1. Thus we have: √ 2 log2 n = O(n · (log2 n)3 ).
2) Since (log2 n)3 = O(n1/3 ), we have:
n · (log2 n)3 = O(n4/3 ).
3) Since 4/3 < 2, we have:
n4/3 = O(100n2 ). 4) Since 100 = O(log2 n), we have:
100n2 = O(n2 log2 n).
5) Since log2 n · log3 n < n when n is sufficiently large, log2 n = O(n/ log3 n). Then we will have:
n2 log2 n = O(n3 / log3 n).
6) We know that n3 / log3 n = O(n3 ) and also that n3 = O(2n ). Thus we have:
n3 / log3 n = O(2n ).
Thus, the final sequence of complexity from low to high is as below:
√ log2 n 2 , n · (log2 n)3 , n4/3 , 100n2 , n2 log2 n, n3 / log3 n, 2n
Page 1 of 3 Sriram Pemmaraju CS:3330 (Pai and Pemmaraju ): Homework 2 Solutions Problem 3
Problem 4 (a) The inner loop runs blog2 ic+1 times for each value of i. Thus the total number of basic operations are:
We can change the base for log function using the change of base formula: ln(n) = log2 n/ log2 e. Then we can apply Stirling’s Approximation to the equation above. Based on Stirling’s Approximation, we have the final running time as:
n + Θ(log2 (n!)) = n + Θ(ln(n!)) = Θ(n ln n + n − n + O(ln n)) = Θ(n ln n).
(b) The inner loop runs n/3 times always. If we count the steps of the outer loop, the total steps will be: n (n + n − 1 + · · · + 1). 3
Using the arithmetic series formula, we have:
n n n(n + 1) (n + n − 1 + · · · + 1) = · = Θ(n3 ) 3 3 2
Problem 5 First we use merge sort to sort the list. This runs in Θ(n log n) time. The resulting list is sorted, with identical numbers bunched together. Then we go through the list in linear time, and count the number of times each distinct element appears in the list. This will take Θ(n) steps. Suppose that there are s dis- tinct elements in the list with k1 , k2 , . . . , ks being their frequecies in the list. Then the total number of pairs is:
k1 k2 ks + + ··· + . 2 2 2 Note that we have computed k1 , k2 , . . . , ks during the linear scan mentioned above. The calculation above also takes linear time since s < n. Thus the total running time of this algorithm is Θ(n log n).
Problem 6 (a) We can see that the outer loop execute exactly n times. The inner loop will execute at most n times every time it is executed. Adding up items from i to j takes at most O(n) steps as well. Storing the result in B[i, j] takes only constant time. Thus the running time of this algorithm is O(n3 ).
(b) Now consider values of i ≤ n/4 and j ≥ 3n/4. The amount of work the algorithm does for these values of i and j is a lower bound on the total amount of work done by the algorithm. The variables i and j take on n2 /16 values together. Now note that for each of these values, j − i ≥ n/2 and hence the summation will take at least n/2 basic operations. The total number of basic operations is n3 /32. This means that the algorithm has running time bounded below by Ω(n3 ).
(c) Consider the following algorithm:
Problem 6 continued on next page. . . Page 2 of 3
Sriram Pemmaraju CS:3330 (Pai and Pemmaraju ): Homework 2 Solutions Problem 6 (continued)
for i = 1, 2, . . . , n B[i, i + 1] ← A[i] + A[i + 1]
for size = 2, 3, . . . , n − 1 for i = 1, 2, . . . , n − size j ← i + size B[i, j] ← B[i, j − 1] + A[j]
This algorithm works since the values B[i, j] were already computed in the previous iteration of the for-loop. It first computes B[i, i + 1] for all i by summing A[i] with A[i + 1]. This requires O(n) steps. For each value of size = 2, 3, . . ., the algorithm computes B[i, j] for j = i + size by setting B[i, j] = B[i, j − 1] + A[j]. For each size, the algorithm runs O(n) steps since there are at most n B[i, j]’s of that “size” (i.e., such that j = i + size). There are also less than n values of size. Thus the algorithm runs in O(n2 ) time.
