1) For this homework, use the following conventions. Definition of Natural Numbe
ID: 3875329 • Letter: 1
Question
1)
For this homework, use the following conventions. Definition of Natural Numbers: the set of natural numbers is the set of non-negative integers, denoted N. That is, N = {0, 1, 2, 3, ). When discussing asymptotic analysis of functions, we will restrict our attention to non-negative, non-decreasing functions with domain N. That is, if f is such a function, then: o (non-negativity) f (n) 20 for all n, m, then f (n) (non-decreasing) If n f (m), and (domain N) the input n of f is in N. Definition of Big-O: A function f (n) is Big-O of g (n), written f (n) - O(9 (n). if there are constant c and M such that f(n) Sc g(n) for all n 2 M Big-O limit Lemma: f(n) = 0(g (n)) if and only if limn-too-= f(n) c for some constant c >0 . .Explanation / Answer
Here as per the definition of Big-O we have to prove first
3*n2 + 2*n + 4 <= c* n2 for all n >= M where M is a constant natural number .
Now , 3*n2 + 2*n + 4 <= 3*n2 + 2*n2 + 4*n2 <= 9*n2 for all n belongs to natural number
So, 3*n2 + 2*n + 4 <= c*n2 for c = 9 and n>=1
Thus, 3*n2 + 2*n + 4 is Big-O of n2
Also , limn->infinity f(n)/g(n) = (3*n2 + 2*n + 4)/(n2) = limn->infinity (3*(n2 /n2) +(2*n)/n2 + 4/n2) = 3 >= 0
Therefore, 3*n2 + 2*n + 4 = O (n2)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.