Difference between Big-O and Little-O Notation

Question

What is the difference between Big-O notation O n  and Little-O notation o n

User · Answer

I find that when I can t conceptually grasp something  thinking about why one would use X is helpful to understand X   Not to say you haven t tried that  I m just setting the stage     stuff you know A common way to classify algorithms is by runtime  and by citing the big-Oh complexity of an algorithm  you can get a pretty good estimation of which one is  better  -- whichever has the  smallest  function in the O  Even in the real world  O N  is  better  than O N     barring silly things like super-massive constants and the like   stuff you know   Let s say there s some algorithm that runs in O N   Pretty good  huh  But let s say you  you brilliant person  you  come up with an algorithm that runs in O N frasl loglogloglogN   YAY  Its faster  But you d feel silly writing that over and over again when you re writing your thesis  So you write it once  and you can say  In this paper  I have proven that algorithm X  previously computable in time O N   is in fact computable in o n     Thus  everyone knows that your algorithm is faster --- by how much is unclear  but they know its faster  Theoretically

User · Answer

f   O g  says  essentially     For at least one choice of a constant k   0  you can find a constant a such that the inequality 0  lt   f x   lt   k g x  holds for all x   a     Note that O g  is the set of all functions for which this condition holds   f   o g  says  essentially     For every choice of a constant k   0  you can find a constant a such that the inequality 0  lt   f x   lt  k g x  holds for all x   a    Once again  note that o g  is a set   In Big-O  it is only necessary that you find a particular multiplier k for which the inequality holds beyond some minimum x    In Little-o  it must be that there is a minimum x after which the inequality holds no matter how small you make k  as long as it is not negative or zero   These both describe upper bounds  although somewhat counter-intuitively  Little-o is the stronger statement  There is a much larger gap between the growth rates of f and g if f   o g  than if f   O g     One illustration of the disparity is this  f   O f  is true  but f   o f  is false  Therefore  Big-O can be read as  f   O g  means that f s asymptotic growth is no faster than g s   whereas  f   o g  means that f s asymptotic growth is strictly slower than g s   It s like  lt   versus  lt    More specifically  if the value of g x  is a constant multiple of the value of f x   then f   O g  is true  This is why you can drop constants when working with big-O notation   However  for f   o g  to be true  then g must include a higher power of x in its formula  and so the relative separation between f x  and g x  must actually get larger as x gets larger   To use purely math examples  rather than referring to algorithms    The following are true for Big-O  but would not be true if you used little-o    x     O x     x      O x     x  x      O 200   x      The following are true for little-o    x     o x    x     o x   ln x    o x    Note that if f   o g   this implies f   O g   e g  x     o x    so it is also true that x     O x      again  think of O as  lt   and o as  lt

User · Answer

In general Asymptotic notation is something you can understand as  how do functions compare when zooming out   A good way to test this is simply to use a tool like Desmos and play with your mouse wheel   In particular   f n    o n  means  at some point  the more you zoom out  the more f n  will be dominated by n  it will progressively diverge from it   g n    T n  means  at some point  zooming out will not change how g n  compare to n  if we remove ticks from the axis you couldn t tell the zoom level    Finally h n    O n  means that function h can be in either of these two categories  It can either look a lot like n or it could be smaller and smaller than n when n increases  Basically  both f n  and g n  are also in O n   In computer science In computer science  people will usually prove that a given algorithm admits both an upper O and a lower bound   When both bounds meet that means that we found an asymptotically optimal algorithm to solve that particular problem  For example  if we prove that the complexity of an algorithm is both in O n  and  n  it implies that its complexity is in T n   That s the definition of T and it more or less translates to  quot asymptotically equal quot   Which also means that no algorithm can solve the given problem in o n   Again  roughly saying  quot this problem can t be solved in less than n steps quot   An upper bound of O n  simply means that even in the worse case  the algorithm will terminate in at most n steps  ignoring all constant factors  both multiplicative and additive   A lower bound of  n  means on the opposite that we built some examples where the problem solved by this algorithm couldn t be solved in less than n steps  again ignoring multiplicative and additive constants   The number of steps is at most n and at least n so this problem complexity is  quot exactly n quot   Instead of saying  quot ignoring constant multiplicative additive factor quot  every time we just write T n  for short

User · Answer

Big-O is to little-o as   is to  lt   Big-O is an inclusive upper bound  while little-o is a strict upper bound   For example  the function f n    3n is    in O n     o n     and O n  not in O lg n   o lg n   or o n    Analogously  the number 1 is      2   lt  2  and   1 not   0   lt  0  or  lt  1   Here s a table  showing the general idea      Note  the table is a good guide but its limit definition should be in terms of the superior limit instead of the normal limit  For example  3    n mod 2   oscillates between 3 and 4 forever  It s in O 1  despite not having a normal limit  because it still has a lim sup  4    I recommend memorizing how the Big-O notation converts to asymptotic comparisons  The comparisons are easier to remember  but less flexible because you can t say things like nO 1    P

User · Answer

The big-O notation has a companion called small-o notation  The big-O notation says the one function is asymptotical no more than another  To say that one function is asymptotically less than another  we use small-o notation  The difference between the big-O and small-o notations is analogous to the difference between  lt    less than equal  and  lt   less than

[algorithm] Difference between Big-O and Little-O Notation

Examples related to algorithm

Examples related to time-complexity

Examples related to big-o

Examples related to asymptotic-complexity

Examples related to little-o