An algorithm is made up of 2 modules M1 and M2. If order of M1 is f (n) and M2…

Explanation:

By definition of order, there exists constants cl, c2,nl, n2 such that

T(n) ≤ cl × f (n),foralln≥nl.

T(n) ≤c2 × g(n),foralln ≥ n2.

Let N= max(nl, n2)andC =max (cl, c2). So,

T(n) ≤C × f (n) for all n ≥N

T(n) ≤ C ×g(n) for all n >N

Adding T(n)≤ C/2 ×(f (n)+g(n) )

Without loss of generality, let max (f (n) ,g (n) ) = f(n).

So,T(n) ≤ C/2 (f(n)+ f (n) ) ≤ C×f(n).

So, order is f (n), which is max (f (n) ,g (n) ), by our assumption.