(b) alogb(n) =nlogb(a) foranybaseb >1
Week 1 Tutorial Sheet (To complete at home during week 1)
Problem1. Show,usingelementarypropertiesofthelogarithmfunction,thatthefollowingidentitiesaretrue (a) log k+1+1=log (k +1)
(a) Wewillmakeuseofthefactsthatlog2(a)+log2(b)=log2(ab),andthatlog2(2)=1. Usingthese,we find
log k +1+1=log k +1+log (2), 22222
=log k+1×2, 22
=log2(k +1),
(b) Let’s use the fact that for any positive real a , we can write a = b logb (a ) since log and exponentiation
as required.
are inverses. We can therefore write
alogb(n) =blogb(a)logb(n). Nowwedigintoourexponentlawsandusethefactthat(xp1)p2 =xp1p2 towrite
blogb(a)logb(n) =blogb(a)logb(n) =blogb(n)logb(a). Finally,sinceblogb(n) =n,wehave
blogb (n)logb (a) =nlogb (a), andhencealogb(n) =nlogb(a) asrequired.
Problem2. Usingmathematicalinduction,provethefollowingidentity: n n ( n + 1 )
i := 1 + 2 + … + n =
2 , for n ≥ 1.
Define the following:
L(n)=1+2+…+n,
R(n)= n(n +1). 2
We want to show that L (n ) = R (n ) for all n ≥ 1. Base Case:
Let n = 1. We have
L(1)=1= 1(1+1) =R(1), 2
as required.
Inductive Case:
Assume that L(k) = R(k) for some k ≥ 1, i.e. assume that
1+2+…+k = k(k +1). 2
We want to prove that L (k + 1) = R (k + 1). Beginning with the left hand side, we wish to express the value of L (k + 1) in terms of L (k ) so that we may make use of the inductive hypothesis. We can do so by writing
L(k +1)=1+2+…+k +(k +1), = L(k)+(k +1).
Now for the most important step, we apply the inductive hypothesis L (k ) = R (k ) to write L(k)+(k +1)=R(k)+(k +1).
From here, we simply use algebra to clean up the resulting expression and obtain the desired result.
R(k)+(k +1)= k(k +1) +(k +1), 2
= k (k + 1) + 2(k + 1) , 22
= k(k +1)+2(k +1), 2
= (k +1)(k +2), 2
= R (k + 1),
and therefore L (k + 1) = R (k + 1) as required. Therefore, by induction on n , it is true that
n n ( n + 1 )
i := 1 + 2 + … + n = 2 , for n ≥ 1. i=1
Problem3. Usingmathematicalinduction,provethefollowingidentity:
n r n + 1 − 1
ri :=1+r +r2 +r3 +…+rn = r −1 , foralln ≥0,r ̸=1. i=0
Define the following:
L(n)=1+r +r2 +r3 +…+rn,
R(n)= rn+1 −1. r−1
WewanttoshowthatL(n)=R(n)foralln≥0,wherer ̸=1. Base Case:
Let n = 0. We have as required.
R(0)= r0+1 −1 = r −1 =1=L(0), r−1 r−1
Inductive Case:
Assume that L(k) = R(k) for some k ≥ 0, i.e. assume that
1+r +r2 +r3 +…+rk = rk+1 −1. r−1
We want to prove that L (k + 1) = R (k + 1). Beginning with the left hand side, we’d like to express L (k + 1) in terms of L (k ) so that we can make use of the inductive hypothesis. We can do so by writing
L(k +1)=1+r +r2 +r3 +…+rk +rk+1, =L(k)+rk+1.
Now we apply the inductive hypothesis that L (k ) = R (k ) to write L(k)+rk+1 =R(k)+rk+1.
Now we use algebra to express the result in terms of R (k + 1). R(k)+rk+1 = rk+1 −1 +rk+1,
= rk+1 −1 + rk+1(r −1),
= rk+1 +rk+1(r −1)−1,
= rk+1(1+(r −1))−1,
r−1 = rk+1r −1,
= r(k+1)+1 −1,
r−1 = R (k + 1),
and therefore L (k + 1) = R (k + 1) as required. Therefore, by induction on n , it is true that
n r n + 1 − 1
ri :=1+r +r2 +r3 +…+rn = r −1 , foralln ≥0,r ̸=1. i=0
Problem4. UsingProblem3,showthatthefollowinginequalityistrueforallintegersn≥1 n 1 :=1+1+1+1+…+ 1 <2
i=02i 248 2n
Noticethat 2i canberewrittenas
n 1 i n
2 ,andthatbysettingr = 12 wecanrewritethisas n rn+1−1 1n+1−1 1n−2 1n
ri==2=2=2−. i = 0 r − 1 12 − 1 − 1 2
1n 1n n 1
Since 2 >0foralln≥1,wehave2− 2 <2,andhenceitistruethat 2i <2asrequired.
Problem5. Theharmonicnumbersaredefinedasthepartialsumsoftheharmonicsequence: H(n):=n 1i =1+12+31+...+n1
We want to determine how this quantity behaves asymptotically, as it frequently arises in algorithm analysis.
(a) ProvethatH(n)>loge(n)
(b) ProvethatH(n)≤loge(n)+1
(c) HencededucethatH(n)=Θ(log(n))1
[Hint: Considertheareaunderthefunction f (x)= x1 usingcalculusandcomparethiswithH(n)geometrically.] Solution
Consider the function f (x ) = x1 for x ≥ 1. A plot of f is depicted below.
WenoticethatthevalueofthesumH(n)=1+12+13+…+n1 isequaltotheareaoftherectanglesdepicted on the following plot.
Since the rectangles are above the curve, their total area is bigger than the area underneath the curve (from x = 1 onwards). The area underneath the curve is given by
and therefore we have
1dx=loge(n+1),
H (n ) > loge (n + 1) > loge (n ),
1RememberthatthenotationΘ(f(n))meansthatH(n)isbothupperboundedbyc1f(n)forsomec1 (itisO(f(n))andlowerboundedby c2 f (n) for some c2 (it is Ω(f (n))).
and therefore H (n ) > loge (n ). Now, consider the same rectangles but all shifted 1 unit to the left.
The leftmost rectangle has area 1, and the others all are all below the curve. The area underneath the curve from 1 onwards is given by
1=loge(n), x
and therefore we have
and therefore we have loge (n ) < H (n ) ≤ loge (n ) + 1. Together, we deduce that H (n ) = Θ(log(n )).
Problem6. ProvethatforallN≥0,
2i =2N+1−1.
H (n ) ≤ 1 + loge (n ),
Define the following:
We want to show that L (n ) = R (n ) for all n ≥ 0.
Base Case:
Let n = 0. We have
L(n)=2i =1+2+4+...+2N ,
R(n)=2N+1 −1.
R(0)=20+1 −1=2−1=1=L(0),
as required.
Inductive Case:
Assume that L(k) = R(k) for some k ≥ 0, i.e. assume that
1+2+4+...+2k =2k+1 −1.
We want to prove that L(k +1) = R(k +1). Beginning with the left hand side, we try to write L(k +1) in
terms of L (k ) so that we can make use of the inductive hypothesis. L(k +1)=1+2+4+...+2k +2k+1,
=L(k)+2k+1.
Now we apply the inductive hypothesis that L (k ) = R (k ) to write
L(k)+2k+1 =R(k)+2k+1.
Finally, we clean up the algebra to obtain the result. R(k)+2k+1.=2k+1 −1+2k+1,
=2×2k+1 −1, = 2(k +1)+1 − 1,
= R (k + 1),
and hence L (k + 1) = R (k + 1) as required. Therefore, by induction on n , it is true that
2i =2N+1 −1, forallN ≥0.
Problem7. Foreachofthefollowingexpressions,writeatightupperboundasn→∞inbig-Onotation:
(a) 3n3 +100n2 +n
(b) n3 log(n)+0.5n4 +100n2
(c) 5n+10log(n)
(d) log(n)+log(log(n))+log(log(log(n)))
(e) 2n log(n)+8n log(n2)
(f) 3n log(n ) + 5n (log(n ))2
(g) log(n)+2log2(n)
(h) 3log(n)+(log(log(n))2
(a) As n gets large, n3 dominates n2 and n, so this is O(n3)
(b) First, n4 dominates n2. Second, we know that n dominates log(n), so consequently n4 dominates
n3 log(n), so this is O(n4)
(c) n is equivalent to n 12 . We know that for any value of k > 0, n k dominates log(n ) (if you’ve taken
MTH1030, try to prove this formally – that is lim log(n ) = 0), so this is O (n ) n→∞ nk
(d) Sincelog(n)isdominatedbyn,havingmanynestedlogsissmallerthanasinglelog,thereforethis is O (log(n ))
(e) Sincelog(n2)=2log(n),bothtermsarethesamemagnitudeO(nlog(n)),hencetheanswerisO(nlog(n)) (O (n log(n 2 )) is also correct, but longer to write and unnecessary)
(f) Sincelog(n)isnotO(1),(log(n))2 dominateslog(n),hencethisisO(n(log(n))2)
(g) Thenotationlog2(n)isshortfor(log(n))2,sobythesamereasoningasabove,thisisO(log2(n)).Note
that this notation does not mean log(log(n ))
(h) Intuitively, we understand that log(n) is the inverse exponential, hence it grows slower than the square function grows fast. This should lead you to believe that log(n) dominates (log(log(n)))2. To seethismoreconcretely,substituten =22k andweobtain3·2k +k2,anditisclearthatthefirstterm dominates, hence this is O (log(n ))
Problem 8. The Fibonacci sequence is defined by the recurrence relation F (n ) = F (n − 1) + F (n − 2), with F(1)=F(2)=1.
(a) Write a Python function that, given a non negative integer n, computes the nth Fibonacci number itera- tively (using a loop). Analyse the time and space complexity of your implementation.
(b) Write a Python function that, given a non negative integer n, computes the nth Fibonacci number recur- sively. Analyse the time and space complexity of your implementation.
Think carefully about the assumptions that you make when analysing the time and space complexity of your algorithms.