COMP4500/7500 Advanced Algorithms & Data Structures Sample Solution to Tutorial Exercise 2 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland August 4, 2014
1. (See CLRS Exercise 1.2-2, p14 [3rd], p13 [2nd], CLR Exercise 1.4-1, p17 [1st])
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, assume insertion sort runs in 10n2 steps, while merge sort runs in 100n lg n steps, where lg n stands for log2 n. For which values of n does insertion sort beat merge sort? You will need to use a bit of algebra, but may then use trial and error if you wish.
How might one write a sorting algorithm which has the advantages of insertion sort for small inputs and the advantages of merge sort for larger inputs? (For an extension, see CLRS Problem 2-1 p39 [3rd], p37 [2nd], CLR Problem 1-2, p17 [1st]).
Sample solution.
Insertion sort is faster than merge sort when
10n2 <100nlgn ≡ n<10lgn
≡ n
Hence 50 < n < 60. The more exact upper bound on n of 58 can be ascertained by trial and error using a calculator. [Note that the use of asymptotic notation avoids this level of detail, and thus avoids the trial-and-error approach.]
Merge sort can be rewritten so that it does an insertion sort on inputs of size 58 or less. The modified merge sort now takes fewer steps than the straight merge sort. What is the complexity of this modified merge sort?
2. (CLRS Exercise 3.1-1, p52 [3rd], p50 [2nd], CLR Exercise 2.1-1, p31 [1st]) A function h is asymptotically nonnegative if there exists an nh such that
(∀n•n≥nh ⇒h(n)≥0)
Let f and g be asymptotically nonnegative functions. Using the definition of Θ-notation, prove that the function max(f(n),g(n)) ∈ Θ(f(n) + g(n)), where for each value of n the function max(f(n),g(n)) returns the maximum of f(n) and g(n). As abbreviations, define functions M and S so that, for all n
M (n) = max(f (n), g(n)) S(n) = f(n) + g(n)
Sample solution. Since f and g are asymptotically nonnegative, there exist nf and ng such that (∀n•n≥nf ⇒f(n)≥0)and(∀n•n≥ng ⇒g(n)≥0).
Taking n0 as the maximum of nf and ng we find
(∀n•n≥n0 ⇒f(n)≥0∧g(n)≥0)
⇒ (∀n•n≥n0 ⇒f(n)+g(n)≥f(n)≥0∧f(n)+g(n)≥g(n)≥0)
≡ (∀n•n≥n0 ⇒S(n)≥f(n)≥0∧S(n)≥g(n)≥0)
⇒ (∀n•n≥n0 ⇒S(n)≥M(n)≥0)
⇒ M∈O(S)
∗Copyright ⃝c reserved August 4, 2014
1
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 2 Similarly,
(∀n•n≥n0 ⇒M(n)≥f(n)≥0∧M(n)≥g(n)≥0) ⇒ (∀n•n≥n0 ⇒M(n)+M(n)≥f(n)+g(n)≥0)
≡ (∀n•n≥n0 ⇒2·M(n)≥S(n)≥0)
≡ (∀n•n≥n0⇒M(n)≥1·S(n)≥0)
2
⇒ M∈Ω(S)
Finally, M ∈ O(S) and M ∈ Ω(S) together imply M ∈ Θ(S).
3. (CLRS Exercise 3.1-3, p53 [3rd], p50 [2nd], CLR Exercise 2.1-3, p31 [1st])
Explain why the statement, “The running time of algorithm A is at least O(n2)”, is content-free.
Sample solution. Let the running time of A be T(n). T(n) ≥ O(n2) means (CLRS p47 [3rd], p46 [2nd], p28 [1st]) that T(n) ≥ f(n) for some function f ∈ O(n2). This is true for any running time T(n), since the function g, such that g(n) = 0 for all n, is in O(n2) and running times are always greater than zero. So the statement tells us nothing about the running time.
4. (CLRS Exercise 3.1-4, p53 [3rd], p50 [2nd], CLR Exercise 2.1-4, p31 [1st]) Is 2n+1 ∈ O(2n)? Is 22n ∈ O(2n)?
Sample solution. 2n+1 ∈ O(2n), but 22n ∈/ O(2n).
Toshowthat2n+1 ∈O(2n),wemustfindconstantsc,n0 >0suchthat:∀n•n≥n0 ⇒0≤2n+1 ≤c·2n.
Now:∀n•n≥1⇒0≤2n+1 =2·2n.
Therefore we can satisfy the definition with c = 2 and n0 = 1.
Alternatively, because the two functions are asymptotically non-negative, we can take the limit of their ratios. If the limit is a non-zero constant, the two functions are the same asymptotic complexity.
2n+1
lim n =lim2=2
n→∞ 2 n→∞
Therefore, 2n+1 ∈ Θ(2n).
To show that 22n ∈/ O(2n) we make use of a proof by contradiction. Assume that 22n ∈ O(2n), i.e., there exist
constants c, n0 > 0 such that
∀n•n≥n0 ⇒0≤22n ≤c·2n
≡ ∀n•n≥n0 ⇒0≤2n ·2n ≤c·2n ≡ ∀n•n≥n0 ⇒0≤2n ≤c.
But no constant is bigger than 2n for all n, so the assumption leads to a contradication and must be false. Alternatively, because the two functions are asymptotically non-negative, we can take the limit of the ratios of
2n and 22n. If the limit is zero then 2n ∈ O(22n) but 2n ∈/ Θ(22n).
2n 1
lim 2n=lim n=0
Now
n→∞ 2 n→∞ 2
2n ∈/ Θ(22n)
≡ 2n ∈/ O(22n) ∨ 2n ∈/ Ω(22n) ≡ 2n ∈/Ω(22n)
≡ 22n ∈/ O(2n)
– property of Θ –as2n ∈O(22n)
– swapping Ω for O
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 3
5. Rank the following functions by order of growth; that is, find an arrangement g1 , g2 , . . . , g25 of the functions satisfying g1 ∈ Ω(g2), g2 ∈ Ω(g3), …, g24 ∈ Ω(g25). Partition your list into equivalence classes such that gi and gj are in the same class if and only if gi ∈ Θ(gj).
(3)n (√2)lgn lg∗ n n2 (lgn)! 2
lg n n3 (lgn)2 lg(n!) 22n n 1
lglgn n·2n nlglgn lnn 2n 2lgn (lgn)lgn 4lgn (n+1)! √lgn
n! 22lgn n nlgn 1
Try to rank as many of the above functions as you can. You may need to refer to CLRS 3.2 or CLR 2.2 for the
definition of lg∗ n and help.
Sample solution. Much of the ranking is based on the following facts:
• exponential functions grow faster than polynomial functions, which grow faster than polylogarithmic functions; • the base of a logarithm doesn’t matter asymptotically, but the base of an exponential and the degree of a polynomial do matter.
√
The following identities are also useful:
(a) (lg n)lg n = nlg lg n
(b) 4lg n = nlg 4 = n2
(c) 2lgn =n
lg n
(d) 2 = n 1
√
(f) (√2)lgn =√n as2(1)lgn =2(lgn)(1) =n1 222
Asymptotic bounds for Stirling’s formula (CLRS (3.18) [3rd], (3.17) [2nd], CLR (2.11) [1st]) are also helpful in ranking the expressions with factorials:
from CLRS (3.16) [3rd], (3.15) [2nd], CLR (2.9) [1st] from CLRS (3.16) [3rd], (3.15) [2nd], CLR (2.9) [1st]
raising (5c) above to power 1 lgn
2√
(e) 2 2lgn =n lgn raising(5d)abovetopower 2lgn
(g) lg(n!) ∈ Θ(n lg n) 2
(lg n)! ∈ Θ((lg n)lg n+ 1 n− lg e ) (j) lg∗ n = min{i ≥ 0 : lg(i) n ≤ 1}
(h) n! ∈ Θ(nn+ 1 e−n )
(i) (lg n)! ∈ Θ((lg n)lg n+ 1 e− lg n)
by substituting lg n for n in (5h) from CLRS (3.16) [3rd], (3.15) [2nd], CLR (2.9) [1st]
CLRS p58 [3rd], p55 [2nd], CLR p36 [1st]
from CLRS (3.19) [3rd], (3.18) [2nd] by dropping constants and low-order terms in (3.18) [3rd], (3.17) [2nd], (2.11)
2 2
We can now rank the functions. Those on the same line are in the same equivalence class, and those higher on the page are Ω of those below them.
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 4 22n
(n + 1)! n!
n·2n 2n
(3)n 2
(lg n)lg n = nlg lg n
(lg n)!
n3
n2 = 4lg n
n lg n and lg(n!)
n = 2lg n (√2)lg n
√
2 2 lg n (lg n)2
see (5h) above
from (5a) above see (5i) above
from (5b) above see (5g) above from (5c) above see (5f) above
see (5e) above
lnn
√
lgn lglgn
lg∗ n 1
n lg n and 1
6. (CLRS Exercise 3.1-2, p52 [3rd], p50 [2nd], CLR Exercise 2.1-2, p31 [1st])
see (5d) above
Show that for any real constants a and b, where b > 0,
(n + a)b ∈ Θ(nb). Sample solution. We need to find constants c1 , c2 , n0 > 0 such that:
∀n•n≥n0 ⇒0≤c1nb ≤(n+a)b ≤c2nb. Notethatfor|a|≤n:n+a≤n+|a|≤2n,andfor|a|≤ 1n:n+a≥n−|a|≥ 1n.
Thusforn≥2|a|:0≤ 1n≤n+a≤2n. 2
22 Taking c1 = (1)b, c2 = 2b and n0 = 2|a| satisfies the definition for Θ.
2
Alternatively, as the two functions are asymptotically non-negative, we can take the limit of their ratio. If it is a non-zero constant, then (n + a)b ∈ Θ(nb).
lim b = lim = lim 1+ n→∞ n n→∞ n n→∞ n
7. (Programming problem)
Algorithms for both insertion sort and merge sort have been studied. You may use any implementations that you wish.
Perform an empirical analysis of these algorithms by running them in order to determine their execution time for different inputs (e.g., the best-case and worst-case inputs for insertion sort) and different sizes of input (eg, 1000, 2000, 4000). Compare your results with the results of the theoretical analysis of these algorithms. (You may find it useful to graph your experimental results.)
You may also like to experiment with profiling the execution of the algorithms.
22
As b > 0, the inequality continues to hold when all parts are raised to the power b: 0≤(1n)b ≤(n+a)b ≤(2n)b ⇒0≤(1)bnb ≤(n+a)b ≤2bnb.
(n+a)b n+ab ab b
=1 =1
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 5
Sample solution. No solution provided. One useful analysis method is to insert statements into the code which count the number of operations executed, and print the counts for differing inputs. Sensible things to count when analyzing sorting algorithms are key comparisons and data moves. Consider the complexity of each of these as functions of the input size.
8. A local minimum of an array segment A[lo..hi] is an element A[k] satisfying, A[k − 1] ≥ A[k] ≤ A[k + 1]
for lo ≤ k ≤ hi. We assume that lo ≤ hi, and that the indices of the whole array, A, range from (at least) lo − 1 through to hi + 1. This allows us to also assume that
A[lo − 1] ≥ A[lo] ∧ A[hi] ≤ A[hi + 1]. (1) This condition guarantees that a local minimum must exist; without (1) the array may be either strictly increasing
or strictly decreasing, in which case there is no local minimum.
(a) DesignanalgorithmforfindingalocalminimumofthearraysegmentA[lo..hi]whichissubstantiallyfaster than the obvious O(n) one in the worst case. Hint: use a divide-and-conquer approach similar to binary search.
Sample solution. The pseudocode algorithm below examines the middle two elements in the array and adjusts either the low or high bound to maintain the condition that A[lo−1] ≥ A[lo] and A[hi] ≤ A[hi+1]. The range of the array to be searched is reduced by one half on each iteration and the algorithm terminates when the low and high bounds are equal. In this state, A[lo − 1] ≥ A[lo] ≤ A[lo + 1].
LOCALMIN(A, lo, hi)
/ Precondition and invariant: lo ≤ hi ∧ A[lo − 1] ≥ A[lo] ∧ A[hi] ≤ A[hi + 1] while lo ̸= hi
mid = (lo+hi)/2 //lo≤mid 1) then there is a comparison made at the midpoint of the range, mid = ⌊(lo + hi)/2⌋, the size of the range to be searched is reduced to some new value n′. The total number of comparisons is given by, C(n) = 1 + C(n′). There are two cases for n′:
if A[mid] ≥ A[mid + 1] then
n′ =hi−(mid+1)+1=hi−⌊(lo+hi)/2⌋=⌊(hi−lo)/2⌋≤⌊(hi−lo+1)/2⌋=⌊n/2⌋;
return lo
where (lo + hi) / 2 = ⌊(lo + hi)/2⌋.
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 6 if A[mid] < A[mid + 1] then
n′ =mid−lo+1=⌊(lo+hi)/2⌋−lo+1=⌊(hi−lo+2)/2⌋=⌈(hi−lo+1)/2⌉=⌈n/2⌉. Taking the larger of these two values for n′ we get,
C(n) ≤ 1 + C(⌈n/2⌉), C(n)≤1+(1+C(⌈⌈n/2⌉/2⌉), C(n) ≤ 2 + C(⌈n/22⌉)
C(n) ≤ 3 + C(⌈n/23⌉)
···
C(n) ≤ k + C(⌈n/2k⌉)
9. (See CLRS Exercise 4.4-6 p93 [3rd], 4.2-2 p72 [2nd], CLR Exercise 4.2-2, p60 [1st]) Argue that the solution to the recurrence
T (n) = T ( n ) + T ( 2n ) + cn 33
where c is a constant, is Ω(n lg n) by appealing to a recursion tree. That is, we would like a lower bound on the solution to the recurrence.
Sample solution. The recursion tree for T (n) consists of a root node with cost cn, a left subtree corresponding to T ( n ) and a right subtree corresponding to T ( 2n ). The left subtree consists of a node with cost cn , a left subtree
Taking k = ⌈lg n⌉ we get
forn>2k−1 C(n) ≤ ⌈lg n⌉ + C(1) = ⌈lg n⌉.
forn>1 forn>2 forn>2 forn>4
333
corresponding to T ( n ), and a right subtree corresponding to T ( 2n ). The right subtree of the root consists of a 99
node with cost 2cn , a left subtree corresponding to T ( 2n ), and a right subtree corresponding to T ( 4n ). This is 399
shown in Figure 4.6 [3rd] 4.2 [2nd] of CLR(S). Try drawing the tree out yourself to another level.
If we sum the costs associated with the nodes across each level of the tree we find the sum is always cn: the root
node has cost cn, so the top level costs cn; the next level has cost cn + 2cn = cn; and the third level has cost
cn +2cn +2cn +4cn =cn. 9999
To get a lower bound on the cost of the tree we need a lower bound on the height of the tree for that part of it that contains complete rows of nodes. The shortest path from the root to a leaf in the recursion tree is
n → (1)n → (1)2n → ··· → 1. 33
Hencetheheightofthetreeisguaranteedtobeatleastk+1,where(1)kn=1.Because(1)kn= n =1when 3 33k
k = log3 n, the height of the part of the tree in which every node has two children is 1+log3 n. Since the values at each of these levels of the tree add up to cn, the solution to the recurrence is at least cn(1 + log3 n) ∈ Ω(n lg n).
10. (See CLRS Problem 4-1, p107 [3rd], p85 [2nd], CLR Problem 4-1, p72 [1st])
Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume that T (n) is constant for n ≤ 1. Make your bounds as tight as possible, and justify your answers. Hint: use the master theorem.
In parts (10a), (10b) and (10d) below, we are applying case 3 of the master theorem, which requires that af ( n ) ≤ b
cf(n) for some c < 1. In each of these parts, f(n) has the form nd. The desired condition is satisfied because
33
n nd ad a af(b)=a b =(bd)n =(bd)f(n)
so af(n) ≤ cf(n) becomes ( a )f(n) ≤ cf(n), and hence we can find a c < 1 to satisfy this provided a bbd bd
(a) T(n)=2T(n)+n3. 2
(2) < 1.
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 7 Sample solution. T (n) = 2T ( n ) + n3 ∈ Θ(n3 ). This is a divide-and-conquer recurrence with a = 2,
2 b=2,f(n)=n3,andnlogb a =nlog2 2 =n.Thequotient
f(n) n3
nlogb a = n =n2 ∈Ω(n2).
As 2 > 0, case 3 of the master theorem applies, and T(n) ∈ Θ(n3). For case 3 we also need to show that af(n) ≤ cf(n) for some c < 1, which using (2) reduces to showing a = 2 < 1.
b bd 23 (b) T(n)=T(9n)+n.
10
Sample solution. T (n) = T ( 9n )+n ∈ Θ(n). This is divide-and-conquer recurrence with a = 1, b = 10 , 10 9
b9
f(n)=n,andnlog a =nlog10 1 =n0 =1.Thequotient
f(n) = n =n∈Θ(n1). nlogb a 1
As 1 > 0, case 3 of the master theorem applies, and T (n) ∈ Θ(n). For case 3 we also need to show that
af(n)≤cf(n)forsomec<1,whichusing(2)reducestoshowing a = 1 = 9 <1. b bd ( 10 )1 10
9
(c) T(n)=16T(n)+n2. 4
Sample solution. T (n) = 16T ( n ) + n2 ∈ Θ(n2 lg n). This is divide-and-conquer recurrence with 4
a=16,b=4,f(n)=n2,andnlogb a =nlog4 16 =n2.Thequotient f(n) n2
nlogb a = n2 =1∈Θ(1). Hence case 2 of the master theorem applies, and T (n) ∈ Θ(n2 lg n).
(d) T(n)=7T(n)+n2. 3
Sample solution. T (n) = 7T ( n ) + n2 ∈ Θ(n2 ). This is a divide-and-conquer recurrence with a = 7, 3
b = 3, f(n) = n2, and nlogb a = nlog3 7. The quotient
f(n) nlogb a
n2 nlog3 7
= n2−log3 7.
As1
=
3 3 nlogb a
the master theorem applies, and T(n) ∈ Θ(n2). For case 3 we also need to show that af(n) ≤ cf(n) for
some c < 1, which using (2) reduces to showing a = 7 < 1. bd 32
(e) T(n)=7T(n)+n2. 2
b
Sample solution. T (n) = 7T ( n ) + n2 ∈ Θ(nlg 7 ). This is a divide-and-conquer recurrence with a = 7, 2
b = 2, f(n) = n2, and nlogb a = nlog2 7. The quotient
f(n) nlogb a
n2 nlog2 7
= n2−log2 7.
As2
=
2 2 nlogb a the master theorem applies, and T (n) ∈ Θ(nlg 7 ).
11. (See CLRS Problem 4-1, p107 [3rd], p85 [2nd], CLR Problem 4-1, p72 [1st])
Give asymptotic upper and lower bounds for T (n) in each of the following recurrences. Assume that T (n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. Hint: use iteration.
(a) T(n)=T(n−1)+n.
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 8 Sample solution. T (n) = T (n − 1) + n ∈ Θ(n2 ). This recurrence can be solved by iteration.
T (n) = T (n − 1) + n
= T (n − 2) + (n − 1) + n
= T (n − 3) + (n − 2) + (n − 1) + n
for n > 1 for n > 2 for n > 3
=T(n−i)+(n−(i−1))+···+(n−2)+(n−1)+n forn>i
= T (n − i) + i−1 (n − j) for n > i
j=0
Taking n − i = 1, we have i = n − 1 and T (n − i) = T (1) ∈ Θ(1). Therefore,
T(n) =
n−2 Θ(1)+(n−j) j=0
n−2 n−2 = Θ(1)+n1−j
j=0 j=0 n−2
= Θ(1)+n(n−1)−j j=1
= Θ(1)+n(n−1)− (n−2)(n−1) 2
= Θ(1)+n2 −n− (n2 −3n+2) 2
n2 n
= Θ(1)+2+2−1
∈ Θ(n2)
√
(b) T(n)=T( n)+1.
Sample solution. T (n) = T (√n) + 1 ∈ Θ(lg lg n). This recurrence can be solved by iteration.
1
T(n)=T(n2 )+1 forn>2
111 =T(n4 )+1+1=T(n22 )+2 forn2 >2
111 =T(n8 )+1+1+1=T(n23 )+3 forn4 >2
11
= T(n2i ) + i for n2i−1 >2
We take the boundary condition n = 2 rather than n = 1 because no amount of repeated square-root-taking
can reduce a number greater than 1 all the way down to 1. The number of times we need to iterate before
1
reaching n ≤ 2 is i (actually ⌈i⌉), where n 2i = 2. Solving for i,
11
n2i =2 ⇐⇒ (2i )lgn=1 takinglgofbothsides
⇐⇒ 2i = lgn ⇐⇒ i = lglgn taking lg of both sides
Hence T (n) = Θ(1) + Θ(lg lg n) ∈ Θ(lg lg n).
A more intuitive way to realise that there are lg lg n steps is to notice that each step (taking the square root,
or raising to the power 1 ) halves the lg of the argument, so the number of steps to reduce lg to 1 (i.e., to 2
lg2) is the lg of the lg.
12. Solve (find an asymptotic upper bound for) the recurrence
T (n) = T (n − a) + T (a) + n
where a ≥ 1 is a constant, by using iteration to generate a guess and then using substitution to verify it.
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 2 (August 4, 2014) 9
Sample solution. Iteration. Because a is a constant, we may assume T(n) is bounded by a constant for n ≤ a: we can take as our bound the maximum of T(n) for n in the range 1 through to a. Hence T(n) ∈ Θ(1), for n ≤ a. Using iteration to solve the recurrence we get
T (n) = T (n − a) + T (a) + n
= (T (n − 2a) + T (a) + (n − a)) + T (a) + n
= T (n − 2a) + 2T (a) + 2n − a
= (T (n − 3a) + T (a) + (n − 2a)) + 2T (a) + 2n − a
= T (n − 3a) + 3T (a) + 3n − (1 + 2)a =(T(n−4a)+T(a)+(n−3a))+3T(a)+3n−(1+2)a forn≥4a = T (n − 4a) + 4T (a) + 4n − (1 + 2 + 3)a
=…
The ith iteration adds n, adds T (a), and subtracts (i − 1) · a, so we have
i−1 T(n)=T(n−i·a)+i·T(a)+i·n−a·j forn≥i·a
j=1
The argument to T is less than the constant a when i = ⌊ n ⌋. Ignoring the floor:
T (n)
= Θ(1)+ a ·Θ(1)+ a ·n−a j j=1
for n ≥ a for n ≥ 2a
for n ≥ 3a
a
n −1 nna
n2 an n = Θ(n)+ a − 2(a −1)(a)
n2 n2 n = Θ(n)+ a −2a+2
n2 1 = Θ(n)+a(1−2)
= Θ(n)+n2 2a
= Θ(n2)
Substitution. To show that T(n) ∈ O(n2), we want to show by induction that T(n) ≤ cn2 for some c ≥ 0. Assume that this is true for all arguments less than some n. Later we will make sure to pick our initial conditions to cover values at least up to a.
T (n) = T (n − a) + T (a) + n ≤c(n−a)2 +ca2 +n
=cn2 −2cna+ca2 +ca2 +n =cn2 −(2cna−2ca2 −n) ≤cn2
2cna−2ca2 −n≥0
⇔ c(2na − 2a2) ≥ n
ind.hypoth.
provided2cna−2ca2 −n≥0
⇔c≥ n 2na−2a2
provided2na−2a2 >0,i.e.,n>a
For n ≥ 2a, the last expression is less than or equal to 1. Since a ≥ 1, any c ≥ 1 works. Pick c large enough to
a
satisfy the initial conditions, i.e., large enough so that T (n) < cn2 for n < 2a.
⇔c≥ 1 2a− 2a2
n