The Gateway to Computer Science Excellence
0 votes
230 views

T1(n)=O(f(n))

T2(n)=O(f(n))

then check T/F?

.T1(n)+T2(n)=O(f(n))

.T1(n)=O(T2(n))

.T1(n)=$\omega$(T2(n))

.T1(n)=${\color{Red} \Theta }$(T2(n))

in Algorithms by (259 points) | 230 views

1 Answer

+1 vote
Best answer

T1(n)=O(f(n))   => T1(n) < c1 * f(n)  where c1 is +ve constant (from Big O Def)

T2(n)=O(f(n))  => T2(n) < c2 * f(n)  where c2 is +ve constant (from Big O Def)

a] True

Since T1(n) + T2(n) < (c1+c2) * f(n), So we can say T1(n) + T2(n) = O(f(n))

b] False

Let T1(n) = n2 and T2(n) = n  and f(n) = n3

Clearly T1(n) >T2(n),So T1(n) = O(T2(n)) is not possible.

c] False

Let T1(n) = n and T2(n) = n and f(n) = n3

Clearly T1(n) < T2(n),So T1(n) = ώ(T2(n))  is not possible.

d] False

Take the same assumptions as above then

You can say, T1(n) < C1 * T2(n) for C1 = 1  but

T1(n) > C2 *T2(n) is not possible for any positive constant

Then T1(n)= Θ(T2(n)) is not possible.

by (475 points)

Related questions

0 votes
3 answers
1
asked Dec 31, 2015 in Algorithms by piyushkr (211 points) | 249 views
0 votes
1 answer
4
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,192 answers
193,988 comments
94,862 users