(30 pts) Answer each of the following questions AND justify your answer. (You ca

Question

(30 pts) Answer each of the following questions AND justify your answer. (You can either use the definition of O, , or the limit approach discussed in class for your justification; if you believe a statement is not true, you may give a counter example).

(a) Is 2n log n = O(n)?

(b) Is 2n log n = (n)?

(c) Is 5n3 + n2 + 4 = (n3)?

(d) Is 5 log2n = (n)? (log base 2)

(e) If f (n) = (g(n)), then does it follow that f (n) + g(n) = O(g(n))?

(f) If f (n) = O(g(n)) then does it follow that g(n) = (f (n))?

(g) Find two functions f (n) and g(n) such that neither f (n) = O(g(n)) nor g(n) = O(f (n)). When you find the functions, justify that in fact they the condition stated.

I'm entirely new to Data Structures and Algorithms, so I could sure use some help on approaching these problems, and even a step-by-step solution.

Explanation / Answer

As per Chegg policy, I am answering to first 4 subparts of the given question:

a.) Let f(n) = 2n logn. Now, for f(n) = O(n), it should follow below statement:

c.n >= 2n*logn

which is not true for any value of C and large values of n. Hence, given statement is false.

b.) Now, for f(n) = Big-omega (n),

c.n <= 2n*logn

which is a true statement for c=1 and n>=2

c.) Let g(n) = 5n3 + n2 + 4. Now, for g(n) = big-theta(n3), it should follow below statement:

c1*n3<=g(n)<=c2*n3

for c1=1 and c2=100 and n>=1, the given statement is true.

d.) Let k(n) = 5 log2n. For k(n) = big-theta(n^1/2), it should follow below equation:

c1*n^(1/2) <= k(n) <= c2*n^(1/2)

which is not true as c1*n^(1/2) can't be less than or equal to k(n) and c2*n^(1/2) can't be greater than or equal to k(n) at the same time for large values of n.

Hope it helps, feels free to comment in case of any query.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.