Tuesday, October 1, 2013

Can someone explain why f(n) + o(f(n)) = theta(f(n))?

Can someone explain why f(n) + o(f(n)) = theta(f(n))?

According to this page:
http://math.stackexchange.com/questions/195935/proof-that-a-function-plus-a-lower-growth-function-is-theta-the-first-function
The statement: f(n) + o(f(n)) = theta(f(n)) appears to be true. Where: o =
little-O, theta = big theta
This does not make intuitive sense to me. We know that o(f(n)) grows
asymptotically faster than f(n). How, then could it be upper bounded by
f(n) as is implied by big theta?
Here is a counter-example:
let f(n) = n, o(f(n)) = n^2. n + n^2 is NOT in theta(n)
It seems to me that the answer in the previously linked stackexchange
answer is wrong. Specifically, the statement below seems as if the poster
is confusing little-o with little-omega.
Since g(n) is o(f(n)), we know that for each ϵ>0 there is an
n&#1013; such that |g(n)|<&#1013;|f(n)| whenever n¡Ýn&#1013;
Thank you.

No comments:

Post a Comment