USA: +1 (725) 712-1730 
Sign in
PLease help to prove,
If T_1(n) = theta(S_1(n)) and T_2(n) = theta(S_2(n)), please prove T_1(n) times T_2(n) = theta(S_1 (n) times S_2(n)).
Expert Answer
By the definiton of Big O, there must be positive constants c1,c2,n1 and n2 such that,
T1(n) <= c1S1(n) when n>=n1
T2(n) <= c2 S2(n) when n>=n2
Let nt =max(n1,n2)
Therefore,
T1(n) <= c1S1(n) when n>=nt
T2(n) <=c2S2(n) when n>=nt
And
T1(n) x T2(n) <= c1S1(n) * c2 S2(n), when n>=nt
T1(n) x T2(n) <= c1 *c2 ( S1(n) x S2(n)), when n>=t
let ct=c1*c2
Finally,
T1(n) *T2(n) <= ct ( S1(n) * S2(n) ), when n>=nt
T1(n) * T2(n) = O (S1(n) * S2(n))
