true or false?

Question

T₁(n)=O(f(n))

T₂(n)=O(f(n))

then check T/F?

.T₁(n)+T₂(n)=O(f(n))

.T₁(n)=O(T₂(n))

.T₁(n)=$\omega$(T₂(n))

.T₁(n)=${\color{Red} \Theta }$(T₂(n))

Answer 1

T₁(n)=O(f(n))   => T₁(n) < c₁ * f(n)  where c₁ is +ve constant (from Big O Def)

T₂(n)=O(f(n))  => T₂(n) < c₂ * f(n)  where c₂ is +ve constant (from Big O Def)

a] True

Since T₁(n) + T₂(n) < (c₁+c₂) * f(n), So we can say T₁(n) + T₂(n) = O(f(n))

b] False

Let T₁(n) = n² and T₂(n) = n  and f(n) = n³

Clearly T₁(n) >T₂(n),So T₁(n) = O(T₂(n)) is not possible.

c] False

Let T₁(n) = n and T₂(n) = n²  and f(n) = n³

Clearly T₁(n) < T₂(n),So T₁(n) = ώ(T₂(n))  is not possible.

d] False

Take the same assumptions as above then

You can say, T₁(n) < C₁ * T₂(n) for C1 = 1  but

T₁(n) > C₂ *T₂(n) is not possible for any positive constant

Then T₁(n)= Θ(T₂(n)) is not possible.