Assessed Preparation
1: 2: 3: 4: 5: 6: 7: 8: 9:
functionCOUNT(A[1..n],target) count = 0
whilei ≤n do
if A[i] = target then count = count + 1
i=i+1 end while
return count endfunction
Week 2 Studio Sheet (Solutions)
Useful advice: The following solutions pertain to the theoretical problems given in the tutorial classes. You are strongly advised to attempt the problems thoroughly before looking at these solutions. Simply reading the solu- tions without thinking about the problems will rob you of the practice required to be able to solve complicated problems on your own. You will perform poorly on the exam if you simply attempt to memorise solutions to the tutorial problems. Thinking about a problem, even if you do not solve it will greatly increase your understanding of the underlying concepts. Solutions are typically not provided for Python implementation questions. In some cases, psuedocode may be provided where it illustrates a particular useful concept.
Problem1. Considerthefollowingalgorithmthatreturnsthenumberofoccurrencesoftargetinthesequence A. Identify a useful invariant that is true at the beginning of each iteration of the while loop. Prove that it holds, and use it to prove that the algorithm is correct.
A useful invariant is that, at the start of iteration i , count is equal to the number of occurrences of target in A[1..i − 1], where we consider A[1..0] to be an empty list.
Note: To prove this loop invariant, we will use induction. First we show that the invariant holds at ini- tialisation, at the start of the first iteration of the loop. This is our base case. Next we assume that the invariant holds at the start of some iteration of the loop, and show that it still holds at the start of the next iteration. At this point we are done, since we have shown that the invariant holds at the start of the first loop, and that if it holds at the start of loop i , it also holds at the start of loop i + 1. This means it holds at the start of every loop, and importantly, that it holds at the start of the loop where the loop condition is false, i.e., it holds when the loop ends.
Proof: At the start of the first iteration, i = 1. Also, count = 0, so count is equal to the number of occur- rences of target in A[1..0], since A[1..0] is an empty list. So the invariant is true at initialisation.
Assume that the invariant holds at the start of k-th iteration. So count is equal to the number of occur- rencesoftargetinA[1..k−1]. Callthisnumberofoccurrencesc. Duringthisiterationoftheloop,i =k. If A[k ] = target, we will increment count, so count will equal c +1, which is the number of occurrences of target in A[1..k ]. If A[k ] ̸= target, then count will not be changed, so count will equal c , which is equal to the number of occurrences of target in A[1..k]. Either way the invariant holds at the start of k + 1t h iteration, that is, count is equal to the number of occurrences of target in A[1..k ]. Since we know the invariant holds at the start, by induction it holds for all values of i , including when i = n + 1, so the invariant holds.
To prove the algorithm is correct, we need to show that at loop termination, count is equal to the number of occurrences of target in A. The invariant tells us that count is equal to the number of occurrences of target in A[1..i − 1], but at loop termination, i = n + 1, so count is equal to the number of occurrences of target in A[1..n] which is all of A. Therefore the algorithm is correct.
Problem 2. Find a closed form solution for the following recurrence relation: T(n−1)+c, ifn>0,
T(n)= b, ifn=0.
To find a closed form for T , we will use the method of telescoping, i.e. we look for a pattern as we substitute
the recurrence relation into itself. For n > 0 we have
T (n ) = T (n − 1) + c , T(n)=(T(n−2)+c)+c =T(n−2)+2c, T(n)=(T(n−3)+c)+2c =T(n−3)+3c.
Continuing the pattern, we see that the general form for T (n ) seems to be T(n−k)+kc, ifn>0,forallk≤n,
T(n)= b, ifn=0.
We want a closed-form solution, so we need to eliminate the term T (n − k ). To do so, we make use of the
fact that we have T (0) = b . By setting k = n , T (n − k ) becomes T (0) and hence we obtain
T (n ) = T (n − n ) + n c , =T(0)+nc,
To prove this is correct, we check to see if our equation satisfies the recurrence. Manipulating T (n ), we
as required. We also have T (0) = b + 0 = b as required. Hence this is a valid solution.
Studio Problems
Problem 3. Write psuedocode for insertion sort, except instead of sorting the elements into non-decreasing
order, sort them into non-increasing order. Identify a useful invariant of this algorithm.
T (n ) = n c + b = (n − 1)c + b + c = T (n − 1) + c ,
We write the usual insertion sort algorithm, except that when performing the insertion step, we loop as long as A[ j ] < key, rather than A[ j ] > key, so that larger elements get moved to the left.
1: functionINSERTION_SORT(A[1..n]) 2: fori=2 to ndo
3: Set key = A[i]
4: Setj=i-1
5: 6: 7: 8: 9:
while j ≥1 and A[j]
To find a closed form for T , we will use the method of telescoping. For n > 0 we have
T (n ) = 3T (n − 1),
T (n ) = 3(3T (n − 2)) = 32 T (n − 2), T (n ) = 32 (3T (n − 3)) = 33 T (n − 3).
Continuing the pattern, we see that the general form for T (n ) seems to be 3kT(n−k), ifn>0,forallk≤n,
T(n)= c, ifn=0.
We want a closed-form solution, so we need to eliminate the term T (n − k ). To do so, we make use of the
fact that we have T (0) = c . By setting k = n , T (n − k ) becomes T (0) and hence we obtain T (n ) = 3n T (n − n ),
=3nT(0), =c3n.
We should now check that this solution is correct. Substituting our proposed solution into the recurrence, we find
3T(n−1)=3(c3n−1)=c(3×3n−1)=c3n =T(n), as required. We also have T (0) = c × 30 = c as required.
Problem 5. Find a closed form for the following recurrence relation:
2T(n−1)+a, ifn>0,
To find a closed form for T , we will use the method of telescoping. For n > 0 we have
T (n ) = 2T (n − 1) + a ,
T(n)=2(2T(n−2)+a)+a =22T(n−2)+(1+2)a, T(n)=22(2T(n−3)+a)+3a =23T(n−3)+(1+2+4)a
Continuing the pattern, we see that the general form for T (n ) seems to be 2kT(n−k)+(1+2+…+2k−1)a, ifn>0,forallk≤n,
T(n)= b, ifn=0.
First, we will evaluate the sum 1+2+…+2k−1. Recall from the Week 1 studio sheet that this sum evaluates
to2k −1,andhencewehave
T(n)= b, ifn=0.
2kT(n−k)+(2k −1)a, ifn>0,forallk≤n,
We want a closed-form solution, so we need to eliminate the term T (n − k ). To do so, we make use of the
fact that we have T (0) = b . By setting k = n , T (n − k ) becomes T (0) and hence we obtain
T(n)=2nT(n−n)+(2n −1)a, =2nT(0)+(2n −1)a,
=2nb +(2n −1)a.
We now verify that this solution is correct by substitution. The recurrence reads
2T (n − 1) + a = 2(2n −1 b + (2n −1 − 1)a ) + a , =2×2n−1b +2×(2n−1 −1)a +a,
= 2n b + 2n a − 2a + a , =2nb +(2n −1)a, =T(n)
asrequired. WealsohaveT(0)=20b +(20 −1)a =b asrequired. Problem 6. Find a closed form for the following recurrence relation:
2Tn+n ifn>1, T(n)= 2
1 if n = 1. State the order of growth of the solution using big-O notation.
To find a closed form for T , we will use the method of telescoping. For n > 1 we have T (n ) = 2T n + n ,
T (n ) = 2 2T n + n + n = 22 T n + 2n , 424
T (n ) = 22 2T n + n + 2n = 23 T n + 3n 848
Continuing the pattern, we see that the general form for T (n ) seems to be T (n ) = 2k T n + k n
We want a closed-form solution, so we need to eliminate the term T n . To do so, we make use of the
2k factthatwehaveT(1)=1.Bysettingk=log (n),Tn becomesT(1)andhenceweobtain
T(n)=2log2(n)T n +nlog2(n)
2log2 (n ) =nT(1)+nlog2(n)
= n + n log2 (n )
In order to check that our solution is correct, we can substitute it back into the original recurrence.
2Tn+n=2n+nlog n+n, 2 2222
=n+nlog n+n, 22
=n+nlog n+1, 22
=n+nlog n+log (2), 222
=n+nlog n ×2, 22
= n + n log2 (n ), =T(n)
as required. We also have that T (1) = 1+log2(1) = 1 as required. The asymptotic behaviour of this function is O (n log(n )).
Problem 7. Use mathematical induction to prove that the recurrence relation
Tn+c, ifn>1, T(n)= 2
b , if n = 1,
hasasolutiongivenbyT(n)=b +c log2(n)foralln =2k forsomek ≥0. Solution
Let’s denote the proposed solution by
T ′(n) = b + c log2 n. WewanttoshowthatT(n)=T′(n)foralln =2k,fork ≥0.
Base Case: Let n = 1.
as required.
Inductive Case:
T(1)=b =b +c ∗0=b +c log2(1)=T′(1)
Assume T (m) = T ′(m) for some m = 2k ,k ≥ 0. Since the recurrence only makes sense for powers of two, we will not attempt to show that T (m + 1) = T ′(m + 1), but rather that T (2m) = T ′(2m). Beginning with
the left hand side,
[Hint: Use part (a)] Solution
T (2m ) = T 2m + c , 2
We invoke the inductive hypothesis that T (m) = T ′(m) so that we can write
T(m)+c =T′(m)+c. Finally, we obtain the desired result by rearranging and using log laws.
T ′ (m ) + c = b + c log2 (m ) + c ,
=b +c log2(m)+c log2(2),
= b + c log2(2m), = T ′(2m),
and hence T (2m ) = T ′ (2m ) as required. Therefore, by induction on n , it is true that T(n)=T′(n), forn =2k,k ≥1.
and hence that b + c log2(n) is a solution for T (n).
Problem 8. Let F (n ) denote the n th Fibonacci number. The Fibonacci sequence is defined by the recurrence
relation F (n ) = F (n − 1) + F (n − 2), with F (0) = 0, F (1) = 1.
(a) Usemathematicalinductiontoprovethefollowingpropertyforn≥1:
1 1n F(n+1) F(n) 1 0 = F(n) F(n−1)
(b) ProvethatF(n)satisfiesthefollowingproperties:
F(2k)=F(k)[2F(k +1)−F(k)] (1)
F(2k +1)=F(k +1)2 +F(k)2 (2)
(a) Definethefollowing:
We want to show that L (n ) = R (n ) for all n ≥ 1. Base Case:
Let n = 1. We have
as required. Inductive case:
1 11 1 1 F(2) F(1) L(1)=1 0 =1 0=F(1) F(0)=R(1),
1 1n F(n+1) F(n) L(n)= 1 0 , R(n)= F(n) F(n−1) .
Assume that L(k) = R(k) for some k ≥ 1, i.e. assume that
1 1k F(k+1) F(k)
1 0 = F(k) F(k−1).
We want to prove that L (k + 1) = R (k + 1). Beginning with the left hand side, we express L (k + 1) in
terms of L (k ) by writing
Invoking the inductive hypothesis that L (k ) = R (k ), we can write 1 1 1 1
and proceed to show that
1 0 = F (n )
F (n − 1) for all n ≥ 1.
1 1k +1 L(k+1)=10 ,
1 1k 1 11 =1010,
1 1 =L(k)1 0.
L(k)1 0=R(k)1 0,
1 1 F(k+1) F(k) 1 1
R(k)1 0= F(k) F(k−1) 1 0, F(k+1)+F(k) F(k+1)
= F(k)+F(k−1) F(k) , F(k+2) F(k+1)
= F(k+1) F(k) , = R (k + 1).
Hence L (k + 1) = R (k + 1) as required. Therefore, by induction on n , it is true that
1 1n F(n+1) F(n)
(b) Frompart(a)wehave
1 1n F(n+1) F(n) 1 0 = F(n) F(n−1).
Substituting n = 2k we have
F(2k+1) F(2k) 1 12k
F(2k) F(2k−1) = 1 0 ,
1 1k 1 1k
F(k) F(k−1) ,
F(k +1)F(k)+F(k)F(k −1) F(k)2 +F(k −1)2
F(k)F(k +1)+F(k −1)F(k) At this point we have obtained the following equalities:
F(k +1) F(k)
F(k) F(k−1) F(k)
F(k +1) F(k +1)2 +F(k)2
F(2k)=F(k)F(k +1)+F(k −1)F(k) F(2k +1)=F(k +1)2 +F(k)2
Notice that Equation (3b) is the required identity for F (2k +1), but Equation (3a) does not look quite right. The identity we are required to prove did not contain F (k −1). To remove this unwanted term, we make use of the definition of F , namely that
F(k +1)=F(k)+F(k −1) =⇒ F(k −1)=F(k +1)−F(k) Substituting into Equation (3a) gives
F(2k)=F(k)F(k +1)+F(k −1)F(k), =F(k)F(k +1)+F(k +1)F(k)−F(k)2, =2F(k)F(k +1)−F(k)2,
= F (k )[2F (k + 1) − F (k )].
as required.
Problem 9. Consider the following recursive function for computing the power function x p for a non-negative integer p .
1: functionPOWER(x,p)
2: if p =0thenreturn 1
3: if p =1thenreturn x
4: if p is even then
5: return POWER(x,p/2)×POWER(x,p/2)
7: return POWER(x,p/2)×POWER(x,p/2)×x
9: endfunction
What is the time complexity of this function (assuming that all multiplications are done in constant time)? How could you improve this function to improve its complexity, and what would that new complexity be?
The time complexity can be formally obtained by solving the following recurrence relation where T (p ) corresponds to the running time of the function for POWER(x,p).
2.T p +c, ifp >1, T(p)= 2
b , if p = 1,
We are not asked to prove the time complexity formally, so we will just make a reasonable argument. The function recurses until p = 0. This will take log2 (p ) levels of recursion since we are halving p each time. For each function call, we make two recursive calls, hence the call tree is a binary tree of height log2(p). Since a binary tree of height h has 2h − 1 nodes, we make O (2log2 (p ) ) = O (p ) function calls, each of which does a constant amount of work. Hence the time complexity is O (p ).
We can improve the time complexity by noticing that the function is actually making the same recursive call twice. Instead of calling POWER(x , p /2) twice, we should just call it once and then square the answer. With this improvement, the height of the call tree is still log2(p), but we only make one function call per level, hence the time complexity will be O (log(p )). The improved implementation might look something like this.
1: functionPOWER(x,p)
2: if p =0thenreturn 1
3: y=POWER(x,p/2)
4: if p is even then
5: return y2
7: return y2 × x
9: endfunction
The recurrence relation for the improved function is
Tp+c, ifp>1, T(p)= 2
b , if p = 1,
and, in our solution to problem 7, we showed that this recurrence relation has the solution T (p ) = b +
c log2 (p ). Hence, the time complexity is O (log(p )).
Problem 10. Consider the typical Merge sort algorithm. Determine the recurrence for the time complexity of
this algorithm, and then solve it to determine the complexity of Merge sort.
Merge sort divides the list in half down the middle, which takes constant time. It then recursively calls itself on both halves. If the complexity of merge sort is given by a function T (n ) where n is the size of the input list, then each of these recursive calls takes T (n ) time.
After both calls finish, the two halves still need to be merged. This can be done with a constant number of operations for each element in the two lists. This means merging takes c n , for some constant c .
The recurrence would therefore be T (n ) = 2T ( n2 ) + c n . Notice that Merge sort takes constant time when
the input is size 1. Call this constant b .
2T(n2)+cn, ifn>1, T(n)= b, ifn=1.
To find a closed form for T, we will use the method of telescoping, as in previous questions.
T(n)=2T(n2)+cn,
T ( n ) = 4 T ( n4 ) + c n + c n
T ( n ) = 8 T ( n8 ) + c n + c n + c n
Continuing the pattern, we see that the general form for T (n ) seems to be
2kT(n )+kcn, ifn>1, T(n)= 2k
b , if n = 1.
We want a closed-form solution, so we need to eliminate the term T ( n ). Setting k = log(n ) gives
2k T(n)=nT(1)+log(n)×cn,
= n b + c n log(n ),
To prove this is correct, we check to see if our equation satisfies the recurrence. Manipulating T (n ), we
n bn cnlog(n2) 2T(2)+cn=2 2 + 2 +cn
= b n + c n (log(n ) − log(2)) + c n = n b + c n × log(n )
as required. We also have T (1) = b + 0 = b as required. Hence this is a valid solution. Notice that is has complexity O (n log(n )), as expected.
Problem 11. Write a Python function that computes F (n ) (the n th Fibonacci number) by using the recur- rences given in Problem 8(b). What are the time and space complexities of this method of computing Fibonacci numbers? You may assume that all operations on integers take constant time and space.
We are not asked for a rigorous proof of the complexity, so we provide a reasonable argument. Each time we recurse, n is halved (plus or minus one), hence the depth of the recursion tree will be log2(n). Since each function call alone requires constant space, the space complexity of such an implementation is O (log(n )). Note that although the recurrence relation has three recursive terms in the first case, it requires only two recursive calls since the term F (k ) is used twice. If the F (k ) term is computed once and reused, we recurse twice at each node, and since the number of nodes in a binary tree of height h is O (2h ), the number of nodes in the tree would be
O 2log2 (n ) = O (n ),
hence the time complexity is O (n ). If we were to naively recurse three times instead of reusing F (k ), then
in the worst case, the number of nodes in the tree would be
O 3log2(n) = O nlog2(3) = O n1.585
which is worse than O (n ). Also see the solution to Problem 15 where master theorem is applied to obtain the time complexity of this approach.
Supplementary Problems
Problem 12. Find a function T that satisfies the following recurrence relation:
T(n−1)+an, ifn>0, T(n)= b, ifn=0.
Write an asymptotic upper bound on the solution in big-O notation.
To find a closed form for T , we will use the method of telescoping. For n > 0 we have T (n ) = T (n − 1) + a n ,
T (n ) = (T (n − 2) + a (n − 1)) + a n = T (n − 2) + a n + a (n − 1),
T (n ) = (T (n − 3) + a (n − 2)) + a n + a (n − 1) = T (n − 3) + a n + a (n − 1) + a (n − 2)
Continuing the pattern, we see that the general form for T (n ) seems to be n
T(n−k)+a i, ifn>0,forallk≤n, i=n−k+1
We want a closed-form solution, so we need to eliminate the term T (n − k ). To do so, we make use of the fact that we have T (0) = b . By setting k = n , T (n − k ) becomes T (0) and hence we obtain
T (n ) = T (n − n ) + a i ,
= T (0) + a i , i=1
= b + a n (n + 1) . 2
Where we have recognised that the sum is 1 + 2 + … + n = n (n +1) . Let’s verify that this is correct by substi- 2
tution. We have
T (n − 1) + a n = b + a (n − 1)n + a n , 2
= b + a (n − 1)n + n , 2
= b + a (n − 1)n + 2n , 2
= b + a n (n + 1) , 2
as required. We also have T (0) = b + a × 0 = b . Finally, the asymptotic behaviour of the solution is O (n 2 ).
Problem 13. Find a function T that is a solution of the following recurrence relation
3T n + n 2 if n > 1, T(n)= 2
1 if n = 1. Write an asymptotic upper bound on the solution in big-O notation.
To find a closed form for T , we will use telescoping. For n > 1 we have T(n)=3T n+n2,
n n2 2 2 n 3n2 2
T(n)=3 3T 4 + 2 +n =3 T 4 + 22 +n ,
2 n n2 3n 2 3 n 32n2 3n2 2 T(n)=33T8+4 +22+n=3T8+42 +22+n.
Continuing the pattern, we see that the general form for T (n )seems to be
k n k 3 i n 2 T(n)=3T2k+ (2i)2,
k n 2 k 3 i
=3T2k+n 4. i=0
Using the formula for the sum of the first t terms of a geometric series, we obtain n 3 k +1 − 1
T(n)=3kT +n2 4 , 2k −1
k n 2 3k+1
=3 T 2k +4n 1− 4 , k n 2 2 3 k +1
=3T2k+4n−4n4 .
We want a closed-form solution, so we need to eliminate the term T n . To do so, we make use of the
2k factthatwehaveT(1)=1.Bysettingk=log (n),Tn becomesT(1)andhenceweobtain
T(n)=3log2(n)T n +4n2−4n23log2(n)+1
2log2 (n ) 4 = 3log2 (n ) + 4n 2 − 4n 2 3 log2 (n )+1
4 Using log laws from the Week 1 studio sheet, we can write
T (n ) = n log2 (3) + 4n 2 − 4n 2 n log2 ( 34 ) 3 4
=nlog2(3) +4n2 −3n2nlog2(34 ). =nlog2(3) +n2(4−3nlog2(43 )).
Tothreedecimalplaces,log (3)=1.585andlog 3=−0.415. Since4−3n−0.415 isbetween1to4forn ≥1, 224
the asymptotic behaviour is
T(n)=O(n1.585)+O(n2), =O(n2).
Problem 14. (Advanced) Consider the recurrence relation T(n)=2T(n)+log2(n).
Although rather daunting at first sight, we can solve this recurrence by transforming it onto one that we have seen before!
(a) Make the substitution m = log2(n) to obtain a new recurrence relation in terms of m, which should look likeT(2m)=…
(b) DefineanewfunctionS(m)=T(2