National University of Modern Languages
Rawalpindi campus
COMPUTER SCIENCE DEPARTMENT
Design and Analysis of
Algorithms
Assignment # 1
SAMPLE SOLUTION
DAA BS/CS-31
Instructions: Copied or shown assignments will be marked zero. 20% Marks deduction for Late
submissions.
Question 1:
Group and rank the following functions by asymptotic growth rate in non-decreasing order
264−1 , n3 , .0001 n2 , 1000 n , Logn2,2log n,nlogn,n 2n,21000,n,n2 logn,¿ Logn,n100 , 4 n , logn 3 , nn ,n3 log n
Solution
Constant=264−1 , 21000
Linear=n , 2log n , 1000 n
Logarithmic= Logn , Logn2 , logn3
Poly-logarithmic= nlogn ,n 2 logn, n3 log n
Polynomial =.0001 n2 ,n 3 , n100
Exponential = ¿
Question 2:
Use the definition of Big-Oh to check that
i. 0.001n3 − 1000n2 − 100n + 5 is O (n3).
To show that 0.001n 3 − 1000n 2 log n − 100n + 5 is O (n 3), we must find constants c > 0
and n0 ≥ 1 such that
0.001n3 − 1000n2log n − 100n + 5 ≤ cn3
As
0.001n3 − 1000n2log n − 100n + 5 ≤ 0.001n3 + 5n3
0.001n3 − 1000n2log n − 100n + 5 ≤ 5.001n3
therefor 0.001n3 − 1000n2 − 100n + 5 is O (n3) for c=5.001 and n0 ≥ 1
ii. n/100= O(n)
To show that n/100= O(n), we must find constants c > 0 and n0 ≥ 1 such that
n/100≤ cn
As n/100 ≤ (1) n
Therefore n/100= O(n) for c=1and n0 ≥ 1
iii. n2 +100nlogn + 10n + 1000=O(n3)
To show that n2 +100nlogn + 10n + 1000= O(n3), we must find constants c > 0 and n0 ≥ 1
such that
n2 +100nlogn + 10n + 1000≤ cn3
As
DAA BS/CS-31
n2 +100nlogn + 10n + 1000≤ n3 +100n3logn3 + 10n3 + 1000n3
n2 +100nlogn + 10n + 1000≤ 1110n3
Therefore n2 +100nlogn + 10n + 1000=O(n3) for c=1110 and n0 ≥ 1
iv. n2 +100nlogn + 10n + 1000=o(n2) // small oh.
To show that n2 +100nlogn + 10n + 1000=o(n2), n2 should be big Oh but not Big theta Θ.
As we know n2 +100nlogn + 10n + 1000=O(n2) for c=1110 and n0 ≥1,
But its also true that n2 +100nlogn + 10n + 1000 = Θ (n2) for c1=1 and c2=1110 as shown
below
(n2) ≤ n2 +100nlogn + 10n + 1000 ≤ 1110 (n2)
Therefore n2 +100nlogn + 10n + 1000 ≠o(n2)
Question 3:
Use the definition of Big-Omega to check that
i. 0.001n3 − 1000n2 − 100n + 5 is Ω(n3).
To show that 0.001n3 − 1000n2 − 100n + 5 is Ω(n3), we must find constants c > 0 and n0 ≥
1 such that
cn3 ≤ 0.001n3 − 1000n2log n − 100n + 5
As
0.0009 n3 ≤ 0.001n3 − 1000n2log n − 100n + 5
therefor 0.00n3 − 1000n2 − 100n + 5 is Ω (n3) for c=0.0009 and n0 ≥ 1
ii. n/100= Ω(n)
To show that n/100= Ω (n), we must find constants c > 0 and n0 ≥ 1 such that
cn≤ n/100
As (1/100) n≤ n/100
Therefore n/100= Ω (n) for c=1/100 and n0 ≥ 1
iii. n2 +100nlogn + 10n + 1000= Ω (n3)
To show that n2 +100nlogn + 10n + 1000= Ω (n3), we must find constants c > 0 and n0 ≥
1 such that
cn3 ≤ n2 +100nlogn + 10n + 1000
As for large values of n this condition will not holds.
Therefore n2 +100nlogn + 10n + 1000 ≠ Ω (n3)
iv. n2 +100nlogn + 10n + 1000= ω (n2) // small omega
To show that n2 +100nlogn + 10n + 1000= ω (n2),
DAA BS/CS-31
we must find constants c > 0 and n0 ≥ 1 such that
cn2 ≤ n2 +100nlogn + 10n + 1000 to hold Ω. It holds with c=1 and n0>1.
But it’s also true that n2 +100nlogn + 10n + 1000 = Θ (n2) for c1=1 and c2=1110 as
shown below
(n2) ≤ n2 +100nlogn + 10n + 1000 ≤ 1110 (n2)
Therefore n2 +100nlogn + 10n + 1000 ≠ ω (n2)
Question 4:
Use the definition of Big-Theta to check that
i. 0.00n3 − 1000n2 − 100n + 5 is Θ (n3).
To show that 0.001n3 − 1000n2 log n − 100n + 5 is Θ (n3), we must find constants c1, c2
> 0 and n0 ≥ 1 such that
c1n3 ≤ 0.001n3 − 1000n2log n − 100n + 5 ≤ c2n3
As
0.001n3 − 1000n2log n − 100n + 5 ≤ 0.001n3 + 5n3
0.001n3 − 1000n2log n − 100n + 5 ≤ 5.001n3
And
0.0009 n3 ≤ 0.001n3 − 1000n2log n − 100n + 5
therefor 0.001n3 − 1000n2log n − 100n + 5 is Θ (n3) for c1=0.0009, c2=5.001 and n0 ≥ 1
ii. n/100= Θ (n)
Yes, it holds the property of Big theta Θ as it holds both the properties of Big Oh O(n) and
Ω(n) as show in question 2 and 3 above.
iii. n2 +100nlogn + 10n + 1000= Θ (n3)
This property of Big theta Θ does not holds because n2 +100nlogn + 10n + 1000 ≠ Ω (n3)
as show in question 3 above.
DAA BS/CS-31
