Department of Computer Science and Engineering, IIT Kanpur
CS210: Data Structures
Dr. R. K. Ghosh
Home | Notice Board | Instructor | TAs | Students | Assignments | Schedule | Lectures | Resources
Solution to Assignment 5
1)Any wave-sort function , which crosses f(n)=n periodically will do . Such function can not be bounded by either O(n) or Ω(n)
But any other function satisfying similar condition will also work.
2) O(f(n))+O(g(n)) = O(f(n)+g(n))=O(max(f(n),g(n)))=max(O(f(n),O(g(n)))
i)O(f(n))+O(g(n)) <= c1f(n)+c2(g(n))
<= c(f(n)+g(n)) , c=greater of c1 and c2
<= O(f(n)+g(n))
ii)O(f(n))+O(g(n)) <= c1f(n)+c2(g(n))
<= (c1+c2) max(f(n),g(n))
<= O(max(f(n),g(n)))
iii)O(f(n)) <= max(O(f(n),O(g(n))))
O(g(n)) <= max(O(f(n),O(g(n))))
hence O(f(n))+O(g(n)) <= max(O(f(n),O(g(n))))
3) f(n)+O(f(n)) >= f(n) and
f(n)+O(f(n)) <= c(f(n)) for some c
hence f(n)+O(f(n)) = Θ(f(n))
4) Σ1/(2k-1)
=Σ(1/k)-Σ(1/2k)
=(ln(2n)+Θ(1))-1/2 ((ln(n)+Θ(1))
=1/2 ln(n)+O(1)
5)Σ(k-1)/2k
=Σ(k-1)(1/2(k-1)-1/2k)
=Σ(k-1)/2(k-1) - (k-1)/2k
=Σ(k-1)/2(k-1) - k/2k + Σ1/2k
=-1/2-1 + 1/(1-1/2)
=-2+2
=0
6)Σ(2k+1)x2k
let s1=Σ2k*x2k
and s2=Σx2k
s1(1/x2-1)=1/(1-x2)
s1= x2/(1-x2)
s21/(1-x2)
hence result is 1/(1-x2)2
7)n!=O(nn)
1*2*3*....n <= n*n*n*....n
n! <= nn
n!=O(nn)
n! <= nn
ln(n!) <= ln(nn)
<= n*ln(n)
= O(n*ln n)
also n! > nn/2 (use induction)
so ln(n!) > (n/2)ln n
hence ln(n!)=Ω(n/2)ln n
hence ln(n!) = Θ (n ln n)
8)[lg n]=s
n < 2(k+1)
[lg n]!/nk > k!/sk .
This sequence is diverging since succesive terms exceed value of 1. Hence term [ln n]! is
polynomially unbounded.
[ln ln n]! = s
nk >= 2k2s
[ln ln n]! >= s!/2k2s
this sequnce converges since the ratio is less then 1/2 . Hence it is polynomially bounded.
9)
Given : f(n)=O(g(n))
f(n) < c g(n) for some c
or 0 <= f(n) <= c g(n)
Given : f(n) < > Ω(g(n))
or f(n) >= c g(n) for no c
therefore f(n) is strictly less than g(n)
so h(n) ={f(n) + g(n)}/2 satisfies our requirement.(Any other function satisfying these condition also deserve merit.)
10)
These are the average cases. For best case or worst case the complexity will be different. You need to specify which complexity you are finding out in your solutions.
Merge Sort = O(n lg n)
Insertion Sort =O(n2)
Bubble Sort = O(n2)
(For details see any algorithm's book.)
11)
This is the order. Few of the function have equal rate of growth and hence given together.
lg(lg*n)
lg*(lg n)
2lg*n
21/2 lg2 n
n1/lg n
lg lg n
lg n
lg2n
nlg n = lg(n!)
n2 = 4lgn
n3
(lg n)!
nlglg n
(3/2)n
2n
en
22n
n!
(n+1)!