Redirected
543 views
0 votes
0 votes
f(n) + O(f(n)) = Θ(f(n)) 

True or not? Explain please

2 Answers

0 votes
0 votes
False.

small o represents all the upper bound values except the tightest upper bound.

so if f(x)=x

then o(f(x)) must be greater than x. it can be x^2 or any higher value it cannot be equal to f(x).

f(x)+o(f(x)) = theta(f(x)) is false as at L.H.S we can have any greater value because of o(f(x)) but at R.H.S we can have only the value equal to f(x).

Related questions