0

http://www.stat.cmu.edu/~cshalizi/uADA/13/lectures/app-b.pdf

The corresponding little-o means “is ultimately smaller than”: $f (n) = o(1)$ means that $f (n)/c \to 0$ for any constant $c$.

Recursively, $g (n) = o(f (n))$ means $g (n)/ f (n) = o(1)$, or $g (n)/ f (n) \to 0$

Notice that $f (n) = o(1)$ means $f (n)/c \to 0$ for any constant $c$.

But in the second case there's no $c$! Where did it 'go'? Shouldn't it be like

$g (n) = o(f (n))$ means $g (n)/ (f (n)) = o(1)$, or $g (n)/ (f (n)*c) \to 0$?

user4205580
  • 2,083
  • Literally, $f(n)=o(1)$ means $f(n)/1\to 0$, from which we deduce $f(c)/c\to 0$ for any non-constant $.$ – Bernard Nov 04 '15 at 14:54
  • 2
    If $f(n)\to 0$ then $f(n)/c\to 0$ for any $c$, and, of course, visa versa. Seems like a bad way to teach little-$o$. Ignore all the stuff about $c$. – Thomas Andrews Nov 04 '15 at 14:55
  • The $c$ in the first definition is just stupid. Saying $f=o(1)$ just means $f\to0$. – David C. Ullrich Nov 04 '15 at 14:57
  • 1
    That PDF is also wrong about what $O$ means - it defines it as $f(n)=O(1)$ if $f(n)\to c$ for some constant $c$. That is just blatantly wrong. (The little-$o$ definition is not technically wrong, just silly, but the big-$O$ definition goes against every other definition that I know of.) – Thomas Andrews Nov 04 '15 at 14:57
  • @ThomasAndrews Preach! – Antonio Vargas Nov 04 '15 at 16:51

1 Answers1

2

There is a lot that is wrong in that PDF. The definition of big-$O$ is flat out wrong, for example.

The definition of little-$o$ is not wrong, per se, but it is certainly pointless. It seems like the writer is trying to create a parallel with the (broken) definition of big-$O$, but the constant $c$ is completely unnecessary for little-$o$.

I see from Wikipedia, though, this text, under "Used in computer science:"

Informally, especially in computer science, the Big O notation often is permitted to be somewhat abused to describe an asymptotic tight bound where using Big Theta Θ notation might be more factually appropriate.

The PDF is slightly closer to this informal "tighter" usage of big-$O$, although even here, the PDF is giving a stronger definition.

Thomas Andrews
  • 177,126