1 vote

If $T1(n) = \Theta(f(n))$

&

$T2(n) = \Theta(f(n))$

Then, Is $T1(n) + T2(n) = O(f(n))$

If yes, then how?

&

$T2(n) = \Theta(f(n))$

Then, Is $T1(n) + T2(n) = O(f(n))$

If yes, then how?

1 vote

Big-O is an upper bound.

Big-Theta is a tight bound, i.e. upper *and* lower bound.

so you can say Ɵ implies O,

Therefore: T1(n)+T2(n) = Ɵ(f(n)) = O(f(n))

for a good read:

https://stackoverflow.com/questions/3230122/big-oh-vs-big-theta

0 votes

T1(n) = ϴ(f(n)) means T1(n) and f(n) are asymptotically equal.

similarly, T2(n) = ϴ(f(n)) means T2(n) and f(n) are asymptotically equal.

so T1(n) + T2(n) is also asymptotically equal to f(n). which is allowed in big Oh.

T1(n) + T2(n) = ϴ(f(n)) and

T1(n) + T2(n) = O(f(n)) both statements are true

similarly, T2(n) = ϴ(f(n)) means T2(n) and f(n) are asymptotically equal.

so T1(n) + T2(n) is also asymptotically equal to f(n). which is allowed in big Oh.

T1(n) + T2(n) = ϴ(f(n)) and

T1(n) + T2(n) = O(f(n)) both statements are true