Question

Justify the fact that if d(n) is O(f(n)) and e(n) is O(g(n)), then the product d(n)e(n) is O(f(n)g(n)).

Answer 1

Let f and g be two functions defined on some subset of the real numbers. One writes

if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x₀ such that

|.

|d(n) | <= k1 |f(n)|    when x>= m1

|e(n) | <= k2 |g(n)|    when x>= m2

m = max (m1,m2)

when x>= m

then

|d(n) | <= k1 |f(n)|

|e(n) | <= k2 |g(n)|

hence

|d(n) | |e(n) | <= k1* k2 |f(n)|   |g(n)|

hence

|d(n) | |e(n) | <= k |f(n)|   |g(n)|    when x> m , k = k1*k2

hence proved

Please rate