The Gateway to Computer Science Excellence

+1 vote

Best answer

T_{1}(n)=O(f(n)) => T_{1}(n) < c_{1 }* f(n) where c_{1 }is +ve constant (from Big O Def)

T_{2}(n)=O(f(n)) => T_{2}(n) < c_{2} * f(n) where c_{2} is +ve constant (from Big O Def)

a] True

Since T_{1}(n) + T_{2}(n) < (c_{1}+c_{2}) * f(n), So we can say T_{1}(n) + T_{2}(n) = O(f(n))

b] False

Let T_{1}(n) = n^{2} and T_{2}(n) = n and f(n) = n^{3}

Clearly T_{1}(n) >T_{2}(n),So T_{1}(n) = O(T_{2}(n)) is not possible.

c] False

Let T_{1}(n) = n and T_{2}(n) = n^{2 } and f(n) = n^{3}

Clearly T_{1}(n) < T_{2}(n),So T_{1}(n) = ώ(T_{2}(n)) is not possible.

d] False

Take the same assumptions as above then

You can say, T_{1}(n) < C_{1} * T_{2}(n) for C1 = 1 but

T_{1}(n) > C_{2} *T_{2}(n) is not possible for any positive constant

Then T_{1}(n)= Θ(T_{2}(n)) is not possible.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.6k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,650 questions

56,192 answers

193,988 comments

94,862 users