Show that fn gn Omax fn gn Show your work and give specifi

Show that f(n) + g(n) = O(max (f(n), g(n))) Show your work and give specific values for c and n_0. Write pseudo-code for an algorithm that given a set S of n integers and another integer x, determines whether or not there exists two elements in S whose sum is exactly x.

Solution

Answer:

Let us go by the definition

O(f(n) + O(g(n)) < = c1 *f(n) + c2*g(n)

< = c( f(n) + g(n)) , let c is greater than c1 + c2

which means < = O(f(n) + g(n))

Now O(f(n) + O(g(n)) < = c1*f(n) + c2*g(n)

< = (c1 + c2) * max ( f(n) , g(n))

Now see :

f(n) < = max(O((f(n) , g(n))))

g(n) < = max(O(f(n),g(n)))

hence Of(n) + O(g(n) = max(f(n), g(n))