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