Question

I need help with question 2, 3 and 4 please. Thanks in advance.

Answer the following questions: 1. Prove that any polynomial of degree k is O (nk 2. By finding appropriate values ofc and no, prove that: f(n) 4 n log2 n + 4 n2 + 4 n iso(n2). 3. Find functions fi and fi such that both fi(n) and /i(n) are O(g(n)), but fi(n) is not OG(n)) 4. Determine whether the following statements are true or false. Briefly justify your answer. a. Iff(n) is (g(n)), then 2r0% (29(n)). b. f(n)g(n) is (min (f (n). g(n)) c. 2na is O(2"), where a is a constant.

Answer 1

2) Given,
f(n) = 4 nlogn + 4 n^2 + 4 n
To find the 'O' notation, we need to find the degreee of the the above polynomic equation. The degree of a polynomial will be the highest degree of individual. The degree of above polynomial is '2'.
so, it will be O(n^2). //Hence proved.

3) There will be many such f1 and f2 functions. Let g(n) be n^2. As, f1 is not O(f2(n)),
We can have f1(n) = n^2+log n+1 and f2(n) = n^2

4) Given, f(n) is 0(g(n)).
We know for any polynomial P, 2^P is 0(2^0(p))
so, 2^f(n) is 0(2^g(n))

4.b) f(n) + g(n) for sum of polynomial big 0(f,g) wil be minimum. so, this is valid.

4.c) for a polynomial we do not consider constant while calculating 0(). so
for 2^na big O is O(2^n)