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

user2445455 picture user2445455 · Oct 2, 2013 · Viewed 7.4k times · Source

According to this page:

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ϵ such that |g(n)|<ϵ|f(n)| whenever n≥nϵ

Answer

user2445455 picture user2445455 · Oct 2, 2013

Update: I've realized the answer to my question

I was confused as to what o(f(n)) was. I thought that o(f(n)) for f(n)=n was, for instance, f(n) = n^2.

This is not correct. o(f(n)) is a function which is upper bounded by f and not asymptotically tight with f. For instance, if f(n)=n, then f(n)=1 might be a member of o(f(n)), but f(n)=n^2 is NOT a member of o(f(n)).