Big Oh notation (how to write a sentence)

I had a test about asymptotic notations and there was a question:

Consider the following:

O(o(f(n)) = o(f(n))

1. Write in words the meaning of the statement, using conventions from asymptotic notation.
2. Is the statement true or false? Justify.

I got it wrong (don't exactly remember what I wrote), but I think is something like:

For any function g(n) = o(f(n)), there is a function h(n) = o(f(n)) so that h(n) = O(f(n)).

Is it correct?

And for (2), I'm not totally sure. Can someone help me with this one too?

Thanks in advan开发者_开发问答ce.

---

I think they were trying to ask a question about the relationship between Big O and little o asymptotic notation.

A) Big O bounding of a Little O bounded function reduces to/imples the Little O bound of that function.

B) True. Big O is a less "strict" bound in that it stipulates that there is an M and an x0 such that f(n) <= M * g(n) for x >= x0, whereas Little O stipulates that for all positive M, there is an x0 such that f(n) is upper-bounded by M * g(n).

Thus the "an M" of Big O is a subset of the "all M" of little O, and so O(o(f(n)) is equivalent to o(f(n)).

For the actual math and not my weak ascii, see the wikipedia page

---

Meaning in plain English : The upper bound of a function that is strictly greater than f(n) is strictly greater than f(n) Your statement could have been written as : For any function g(n)=o(f(n)) there exists h(n)=O(g(n)) which implies h(n) is also o(f(n)) => O(g(n)) = o(f(n)) => O(o(f(n))) = o(f(n)) Yes the statement is correct. (of course the above statement assumes all the correct constants and the use of "strictly greater is fr readability and understanding : it should be "a strict upperbound")

---

Sorry if this seems like a bit of an aside, but I think it's a dodgy question (as Alexandre C has alluded to) as it's a pretty big abuse of notation.

The way big-O notation is commonly taught (especially in a computer science class) is as if O(f(n)) is a function. This should set off some alarm bells, as the statements "n = O(n)" and "2n = O(n)" are both true, but "n = 2n" is not. If we want to say "f(n) is big-O of g(n)" we technically shouldn't be saying "f(n) = O(g(n))", rather we should say "f(n) is an element of O(g(n))". The former is just a convenient shorthand.

So back to the actual question, O(o(f(n))) doesn't really mean a whole lot (or at least I've never seen a formal definition of big-O of a set of functions). But I guess the logical way to interpret it would be as per enjay's answer, with g(n) = o(f(n)).