Comp 332: Analysis of Algorithms
Homework #2
Due Thursday, 9/14/2023
1. For each of the following algorithms, indicate (i) a natural size metric for the inputs, (ii) its
basic operation, and (iii) whether or not it has an every-time complexity (yes/no).
a) Computing the sum of n numbers
b) Computing n!
c) Finding the largest element in a list of n numbers
2. Consider a variation of Sequential Search that scans a list to return the number of
occurrences of a given search key in the list. Does its efficiency differ from the efficiency of
classic Sequential Search? Explain.
3. Given a list of n numbers, suggest how any sorting algorithm could be augmented so that its
best-case number of comparisons is just n – 1, that is, so that Cbest(n) = n – 1. Do you think it
would be a worthwhile addition to any sorting algorithm?
4. For each of the following pairs of functions, indicate whether f (n) has a lower, same, or
higher order of growth (to within a constant multiple) than g (n) . You do not need to prove
your statements, although it might be nice to provide some explanation.
a) f (n) = n(n+1) and g (n) = 2000n2
b) f (n) = 100n2 and g (n) = 0.01n3
c) f (n) = log 2 n and g (n) = ln(n)
d) f (n) = log 22 n and g (n) = log 2 n 2
e) f (n) = 2n−1 and g (n) = 2n
f) f (n) = (n – 1)! and g (n) = n!
5. Use the informal definitions of O, Θ, and Ω to determine whether the following assertions
are True or False. You do not need to justify your statements.
a) n(n + 1)/2 ∈ O(n3)
b) n(n + 1)/2 ∈ O(n2)
c) n(n + 1)/2 ∈ Θ(n3)
d) n(n + 1)/2 ∈ Ω(n)
6. a) Using the definition of O, show that 6n2 + 20n ∈ O(n3).
b) Using the definition of Ω, formally prove that 6n2 + 20n ∉ Ω(n3)
c) Using the definition of Θ, show that n2 + 3n3 ∈ Θ(n3)
7. Develop pseudocode for an algorithm to find all the common elements in two sorted arrays
of numbers. For example, for A = [2, 5, 5, 5, 5] and B = [2, 2, 3, 5, 5, 7], the output should be
C = [2, 5, 5]. Assume that the input array A has length m, the input array B has length n, and
that m ≤ n. Your algorithm should take advantage of the fact that the lists are sorted. Please
finish the pseudocode below.
ALGORITHM: commonElements(A[0..m–1], B[0..n–1])
// Returns an array C of all common elements of A and B
// Input: two sorted arrays A[0..m–1] and B[0..n–1] where m ≤ n.
// Output: an array C that contains all common elements of A and B
Initialize array C[0..m–1]
k←0 // number of elements in common
8. For each of the following functions, indicate the class Θ(g(n)) the function belongs to. Make
a guess (being sure to use the simplest g(n) possible), and then formally prove your bound.
This is similar to Example 2.12 on page 27 of the Course Notes.
a) (n 2 + 1)10
b) 10n 2 + 7 n + 3
Recommended Problems (not to be turned in):
9. What is the maximum number of comparisons your algorithm makes in Exercise 8?
10. For each of the following functions, indicate how much the function’s value will change if its
argument is increased fourfold.
a) log 2 n
b) n
c) n
d) n2
e) n3
f) 2n
