selfas

Question

f(n) + O(f(n)) = Θ(f(n)) 

True or not? Explain please

Comments

ok.
From theta, we get  value greater than function and Value smaller than function  and value which are equal to function.
From small o, we get only value greater than function.
hence this relation  is true for asymptotically positive values(value greater than function) as stated in question.

Addition of the above two function gives maximum from them. and maximum is small o (<) .

 In theta we have   (> , < , =).

---

i did nt get u..:(

---

Let us take a function k(n) = o (f(n)), means for all c > 0 there exists some k > 0 such that 0 ≤ k(n) < c*f(n) for all n ≥ k.

f(n) + o(f(n) ≃  f(n) + c * f(n) in which the leading term is f(n)

f(n) = ⊖ f(n) which is true.

Answer 1

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).

Answer 2

No this is not true.

Please check out the below link.

https://stackoverflow.com/questions/19128893/can-someone-explain-why-fn-ofn-thetafn