Tutorial
0. Sums
(a)
(b)
(c)
(d)
(e)
(f)
COMP20007 Design of Algorithms
Week 3 Workshop Solutions
n
1=1+1+…+1=n
n n(n + 1)
i=1
n times
i = 1 + 2 + · · · + n = 2 (Triangle numbers formula) i=1
n n n n(n+1) (2i+3)=2i+3=2× 2
+3×n=n2 +4n
i=1
i=1 i=1
n−1 i n−1
1 = (i + 1) = 1 + 2 + · · · + n =
i=0 j=0 i=0
n(n+1) 2
n m n(n+1)m(m+1) ij= i j =
n m
nm(n+1)(m+1) 224
i=1 j=1
i=1 j=1
n
xk =
k=0
=
(Geometric series)
1 − xn+1 1 − x
1. Complexity classes
(a) 12n2 ∈ Ω(3n) – ignore constants, n2 grows faster than n
(b) n2 + n ∈ Θ(3n2 + log n) – ignore constants, the fastest growing terms are both n2
(c) n log n ∈ O n √n – ignoring constants the difference here is log n vs. √n 4
(d) log(10n)∈Θ(log(n2))–usingloglawsf(n)=log10+lognandg(n)=2logn
(e) (logn)2 ∈ Ω(log(n2)) – we can see that (logn)2/(2logn) = 12 logn so f(n) grows faster
(f) log n ∈ Θ(lnn) – using change of base formula log n = 1 10 10 ln10
lnn
(g) 2n ∈ O(3n) – unlike logarithms, the base in the exponential changes the growth rate
(h) n!∈O(nn)–1×2×···×n∈O(n×n×···×n)butnotviceversa 1
2. Sequential search
(a) general (i.e., all possible inputs): the best case for sequential search is when the element we’re searching for is at index 0. So Cbest(n) = 1. Also Cworst(n) = n occurs when the element is not in the array. So Cbest(n) ≤ C(n) ≤ Cworst =⇒ C(n) ∈ Ω(1) and C(n) ∈ O(n).
(b) the best case: in the best case Cbest(n) = 1 so Cbest ∈ Θ(1).
(c) the worst case: in the words case Cworst(n) = n so Cworst ∈ Θ(n).
(d) the average case: let the probability of the element being in the array be p. If the element is not in the array the cost is n. If the element is in the array we assume it’s equally likely to be in any of the n indices. Taking the average of the number of comparisons when the element is in each index:
1 (1 + 2 + · · · + n) = 1 · n(n + 1) = n + 1 . nn22
So the cost is n+1 with probability p, or n with probability (1 − p), i.e., 2
Caverage(n) = p × n + 1 + (1 − p) × n. 2
Since p is a constant here, Caverage ∈ Θ(n).
3. Solving recurrence relations Solve the following recurrence relations, assuming T (1) = 1.
(a) T(n)=4n−3
T (n) = T (n−1)+4 means T (n−1) = T ((n−1)−1)+4 = T (n−2)+4, and T (n−2) = T (n−3)+4, and so on. Repeatedly substitute into the first equation, until the pattern becomes clear. Then, produce the base case to eliminate T.
T (n) = T (n − 1) + 4
= T (n − 2) + 4 + 4
. .
= T (n − 3) + 4 + 4 + 4 = T (n − k) + k × 4
= T (n − (n − 1)) + (n − 1) × 4 = T (1) + (n − 1) × 4
= 1 + 4n − 4
= 4n − 3
(starting to see the pattern?)
(bring in the base case)
2
(b) T (n) = n(n + 1) 2
T (n) = T (n − 1) + n
= T (n − 2) + (n − 1) + n
= T (n − 3) + (n − 2) + (n − 1) + n
.
= T (n − k) + (n − (k − 1)) + · · · + (n − 2) + (n − 1) + n
.
= T (n − (n − 1)) + (n − (n − 1 − 1)) + · · · + (n − 2) + (n − 1) + n = T (1) + (n − n + 1 + 1) + · · · + (n − 2) + (n − 1) + n
= 1 + 2 + · · · + (n − 2) + (n − 1) + n
= n(n + 1)
2 (c) T (n) = 2n − 1
T(n) = 2T(n−1)+1
= 2(2T(n − 2) + 1) + 1 = 22T(n − 2) + 2 + 1 =22(2T(n−3)+1)+2+1=23T(n−3)+22 +2+1
.
=2kT(n−k)+2k−1 +···+22 +2+1 .
=2(n−1)T(n−(n−1))+2(n−1)−1 +···+22 +2+1 =2n−1T(1)+2n−2 +···+22 +2+1
(triangle numbers)
=2n−1 +2n−2 +···+22 +2+1
= 2n − 1 (sum of powers of 2 is the next power of 2, minus 1)
4. k-Merge
(sizes n and n) will take 2n steps. Merging this list with the next list (sizes 2n and n) will take 3n steps. The next will be 4n steps, and so on, until the last list of n is merged with the rest of the (k − 1)n items, taking kn steps. In total,
2n + 3n + 4n + · · · + kn = n(2 + 3 + 4 + · · · + k) Simplifying by recognising the triangle numbers, we’re looking at Θ(k2n):
n(2 + 3 + 4 + · · · + k) = n(1 + 2 + 3 + 4 + · · · + k) − n = nk(k + 1) − n ∈ Θ(k2n) 2
A faster algorithm would use the merging strategy from mergesort, merging the lists in pairs. First, merge k/2 pairs of length n lists, resulting in k/2 lists of length 2n (and taking k/2 × 2n = kn steps). Next, merge k/4 pairs of length 2n lists, resulting in k/4 lists of length 4n (and taking k/4 × 4n = kn steps). Continue, a total of log k times, and you will have one list of length kn in Θ(kn log k) time.
Merging two lists of sizes a and b takes about a + b steps. Merging the first two lists
5. Mergesort complexity (optional) Recurrence relation:
T (n) = T n + T n + Θ(n) = 2T n + Θ(n)
222 3
where T (n) is the runtime of mergesort sorting n elements. The first T ( n2 ) is the time it takes to sort the left half of the input using mergesort. The other T ( n2 ) is the time it takes to sort the right half. Θ(n) is a bound on the time it takes to merge the two halves together.
We haven’t seen the master theorem in class yet, and for this question we aren’t required to solve the recurrence relation. However if we did want to solve this we can recognise that this recurrence relation fits the master theorem, with a = 2, b = 2, and d = 1.
logb(a) = log2(2) = 1 = d so, by the master theorem, T (n) ∈ Θ(n log n).
4