(i) Give four properties of Big – O Notations. (4)
(ii) Give the graphical notations of Big-O estimations for the following functions:
log2 n , n , n log2 n , n2, n3, 2n 

Ans:
(i) Four properties of Big-O notations are:
1. Reflexivity
2. Symmetry
3. Transpose Symmetry
4. Transitivity
Reflexivity:
f(n)=O(f(n))
Symmetry and Transpose Symmetry
f(n)=O(g(n)) iff g(n)=W(f(n))
Transitivity
f(n)=O(g(n)) and g(n)=O(h(n)) implies f(n)= O(h(n))
(ii)
n
Sqrt
n
n! n2 n3 n4 logn nlogn 2n
2 1.41 2 4 8 16 0.30103 0.60206 4
3 1.73 6 9 27 81 0.477121 1.431364 8
4 2.00 24 16 64 256 0.60206 2.40824 16
5 2.24 120 25 125 625 0.69897 3.49485 32
6 2.45 720 36 216 1296 0.778151 4.668908 64
7 2.65 5040 49 343 2401 0.845098 5.915686 128
8 2.83 40320 64 512 4096 0.90309 7.22472 256
9 3.00 362880 81 729 6561 0.954243 8.588183 512