Give the asymptotic values of the following functions, using the -notation: (b)

Question

Give the asymptotic values of the following functions, using the -notation: (b) 3+2n2 1/(log2n) (c) n(7n3 log n + 9n logs n) + 15n3 (d) n22" + 13n+4n3 log n (e) n53 +n4" Justify your answer. (Here, you don't need to give a complete rigorous proof. Give only an informal explanation using asymptotic relations between the functions n, log n, and c".) Submission. To submit the homework, you need to upload the pdf file into ilearn by 8AM on Thursday, October 12, and turn-in a paper copy in class Reminders. Remember that only LTEX papers are accepted.

Explanation / Answer

As per big-oh definition, f(n) = O(g(n)) iff c*g(n) >0 and f(n) = O(k(n)) if k(n) is the term which affects the result most.

a.) Since, 1/2*n^5 is the most dominant term, therefore, f(n) = O(n^5).

b.) Similarly, for increase in value of n value of function will decrease Therefore, it will never be more than a constant. Hence, f(n) = O(1).

c) Most dominating term in this case is 7*n^4*log n. Therefore, f(n) = O(n^4*log n)

d.) similarly, f(n) = O(n^2*2^n)

e.) In this case, if you check for very large values of n, n*4^n will be the dominating term (note: check the values of function after taking log). Hence, f(n) = O(n*4^n).

Hope it helps, do give your valuable response.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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