2

I had a question about Big O vs little o notation. It seems intuitively, that Big O is like <= while little o is like <. Does that mean that if something is little o of f(n), it is also Big O of f(n), in the same way that if i < j, i <= j? Thanks for your help.

user3026230
  • 21
  • 1
  • 4

1 Answers1

6

Yes. Little-oh implies Big-Oh.

Big o table

Community
  • 1
  • 1
Craig Gidney
  • 17,763
  • 5
  • 68
  • 136
  • Wouldn't it be the other way around, that Little-o implies Big-O, as Little-O is strict and Big-O is not? As in, 5 <= 5, but not 5 < 5? Sorry to contradict you if that was a simple typo. – user3026230 Sep 17 '14 at 04:38
  • 2
    +1: Though as mentioned it might be good to state explicitly that while little-oh implies big-oh, big-oh does not imply little-oh. – Nuclearman Sep 17 '14 at 04:42
  • 1
    The "limit definition" doesn't match the usual definition of O. Eg: "f(n) = n if n is even, 0 otherwise" has f(n) <= n, and therefore f = O(n), but lim(f/n) doesn't exist. – Paul Hankin Sep 17 '14 at 09:51
  • @Anonymous *Technically* there should be a `sup` around the functions in the definition to mean "largest value so far". But you rarely run into functions that keep dipping like your example when analyzing algorithms in practice, and always ignore it when they do, so I use the simplified slightly-wrong definition when explaining. – Craig Gidney Sep 17 '14 at 14:31
  • @Strilanc counterexamples are the running time of mergesort being O(n log n) and the depth of a perfectly balanced binary tree being O(log n). They don't dip to 0 like the extreme example, but they vary enough that the limits don't exist. – Paul Hankin Sep 17 '14 at 21:46
  • What is the source of this cheat sheet image? – Rahul Raj Purohit Sep 09 '22 at 01:50