Uttrakhand Asst. Professor Exam-66

Question

Let $T_1(n) = O (f(n))$ and  $T_2(n) = O (g(n))$, then ${T_1(n)}.{T_2(n)}$ will be

• A. $O(f(n).g(n))$                                               
• B. $O(f(n))+O(g(n))$
• C. $O(f(n))-O(g(n))$                                        
• D. None of the above

Answer 1

$T_1(n) = O(f(n))$ & $T_2(n) = O(g(n))$

By the definition of $O$- notation ,

$T_1(n)$ $\leq$ $c_1.(f(n))$ & $T_2(n)$ $\leq$ $c_2.(g(n))$

Now, 

Assuming, $c_1.c_2 = C$

∴ $T_1(n).T_2(n)$ $\leq$ $(c_1.f(n)).(c_2.g(n))$

Or, $T_1(n).T_2(n)$ $\leq$ $(c_1.c_2).(f(n).g(n))$

Or, $T_1(n).T_2(n)$ $\leq$ $(C).(f(n).g(n))$

Or, $T_1(n).T_2(n)=O(f(n).g(n))$

∴ ${T_1(n)}*{T_2(n)}$ = $O(f(n).g(n))$   option A)