search
Log In
1 vote
633 views
If $T1(n) = \Theta(f(n))$

&

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

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

If yes, then how?
in Algorithms
edited by
633 views

2 Answers

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

Related questions

2 votes
1 answer
1
352 views
Given h(n) < f(n) < g(n). statement 1: h(n)=O(f(n)); g(n)=Ω(f(n)) Statement 1 is True / False?
asked Jan 21, 2018 in Algorithms hacker16 352 views
1 vote
0 answers
2
356 views
Let f(n), g(n) & h(n) be 3 non-negative functions defined as follows: $f(n) = O(g(n))\; \; \; g(n) \neq O(f(n))$ $g(n) = O(h(n))\: \: \: h(n) = O(g(n))$ Which of the following is false? (A). f(n) + g(n) = O(h(n)) (B). f(n) = O(h(n)) (C). $h(n) \neq O(f(n))$ (D). $f(n).h(n) \neq O(g(n).h(n))$
asked Aug 23, 2017 in Algorithms Victor0001 356 views
1 vote
2 answers
3
286 views
Consider the following statements: $(1)$ Any two functions $f,g$ are always comparable under big Oh,that is $f=O(g)$ or $g=O(f)$ $(2)$ If $f=O(g)$ and $f=O(h)$ then $g(n)=\theta(h)$ $A)$ $(1)$ is true $(2)$ is false $B)$ $(1)$ is false $(2)$ is true $C)$ Both are false $D)$ Both are true
asked Nov 1, 2018 in Algorithms Lakshman Patel RJIT 286 views
1 vote
0 answers
4
304 views
int unknown(int n) { inti, j, k = 0; for (i = n/2; i<= n; i++) for (j = 2; j <= n; j = j * 2) k = k + n/2; return k; } What is the returned value of the above function? (GATE CS 2013) (a) Ѳ(n2) (b) Ѳ(n2 log n) (c) Ѳ(n3) (d) Ѳ(n3 log n)
asked Nov 14, 2017 in Algorithms NIKU 304 views
...