little oh notation as the limit of n goes to infinity

Question

Hi all,

I'm just trying to understand how in little o notation this is true:

f(n)/g(n) as n goes to infinity = 0?

Can someone explain that to me?

I do get the idea that f(n) = o(g(n)) means that f(n) grows no faster then cg(n) for all constants c > 0.

I just don't get the bit in bold above.

Answer 1

http://en.wikipedia.org/wiki/Little_o_notation#Little-o_notation

You've left something out, namely your definitions for f and g.

It would appear that the precondition for the bolded statement is g(n) in o(f(n)).

According to the Wikipedia article, f(n) = o(g(n)) means that f grows slower than cg(n) for all positive constants. So f(n) is not in o(f(n)).

Answer 2

There was a great episode of BBC's Horizon (titled 'To Infinity and Beyond') recently that explained this.