discrete mathematics question 6 Big and big ahera m us work

discrete mathematics
question 6

Big and big ahera m us work with rough estimates. Huvi they are vey provide careful On the contrary, ot a license to enough to omis sustentents arouz cone aparative rates of growth. elevant details tight enouagh to cal 5. State wherher each of the following is true or false. in each case give a reason for your answer over than your (a) 2\" O (2\") (c) 2 O (2\'\') (d) (200m) (e) 2 (h) (200n) 6. Repeat Exercise 5 for (a) log in o( n) (b) lo (n (d) (vn 1) O(log2 n) (c) log, n 7. True or false. In each case give a reason n the (a) 40t O(2\") (b) (40n)

Solution

Q6)

a) log2 to the base 73 n will be greater than n, hence the minimum order will be O(n)

Hence the statement is FALSE

b) log2(n^(73) = O(log2 n)

The statement is TRUE

Since log2(n^73) = 73log2(n), hence if we keep the value of c as 74 in the expression, f(n)<= c.g(n), hence the statement will be true

(c) log2n^n = nlog2n, which is not bounded by O(log2n)

Hence the statement is FALSE

(d) (n^(0.5) + 1)^4 = O(n^2)

TRUE,since the maximum power in the expression will be (n^0.5)^4 = n^2

Hence it will be bounded by O(n^2)