Using the definition of bigO show that fn elementof Ogn for

Using the definition of big-O, show that f(n) elementof O(g(n)) for the following pair of functions (i.e. find constants C and k, and show that they satisfy the definition of big-O). f(n) = 3n + 7, g(n) = n. f(n) = n log n, g(n) = n^2.

Solution

(a) .f(n)=3n+7   ,g(n)=n

Choose k = 1.

Assuming n > 1, then

f(n)/g(n) = 3n+7/n < 3n+7n/n =10n/n =10

Choose C = 10. Note that 7 < 7n.

Thus, 3n + 7 is O(n) because 3n + 7 10n whenever n > 1.

(b).f(n)=nlogn, g(n)=n^2

   f(n)<=c*g(n)   where n>1 and n<1

   nlogn<= c*n^2

   logn<=n

(because logn<n/logn<n^1/2<n<nlogn<n^2<n^3)