Question

Use the definition of 0 to show that 5n^5 +4n^4 + 3n^3 + 2n^2 + n 0(n^5).Use the definition of 0 to show that 2n^2 - n+ 3 0(n^2).Let f,g,h : N 1R*. Use the definition of big-Oh to prove that if/(n) 6 0(g{n)) and g(n) 0(h{n)) then/(n) 0(/i(n)). You should use different letters for the constants (i.e. don't use c to denote the constant for each big-Oh).

Answer 1

2.5n^{5 _<} 5n^{5 ₊}4n^{4 ₊}3n^{3 ₊} 2n^{2 ₊} n ^_< 5n^{5 ₊}4n^{5 ₊}3n^{5 ₊} 2n^{5 ₊}  n⁵

^i.e. 5n^{5 _<} 5n^{5 ₊}4n^{4 ₊}3n^{3 ₊} 2n^{2 ₊}  n _^< 15n⁵

^i.e.5n^{5 ₊}4n^{4 ₊}3n^{3 ₊} 2n^{2 ₊}  n belongs to Theta of n³

^3. n^{2 _<}2n^{2 _-} n_⁺  3 < 2n^{2 _-} n^{2 ₊}3n²

^i.e.   n^{2 _<}2n^{2 _-} n_⁺  3 < 4n²

^i.e  2n^{2 _-} n_⁺  3 belongs to Theta of n²

^4.

Using Big O definition: f = O(g) iff exist c, n0 > 0 such that forall n >= n0 then 0 <= f(n) <= cg(n) g = O(h) iff exist k, n1 > 0 such that forall n >= n1 then 0 <= g(n) <= kh(n) Now take the last unequality and divide all members by c: 0 <= f(n)/c <= g(n) and we can substitute g(n) in the second inequality: 0 <= f(n)/c <= kh(n). Finally multiply all members byc and you obtain 0 <= f(n) <= kch(n) that is the definition of f = O(h): f = O(h) iff exist j, n2 > 0 such that forall n >= n2 then 0 <= f(n) <= jh(n) In our case it is: n2 = max(n0, n1) and j = ck.