What is the difference between Big-O notation (`O(n)`

) and Little-O notation (`o(n)`

)?

f ∈ O(g) says, essentially

For

at least onechoice of a constantk> 0, you can find a constantasuch that the inequality f(x) < 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

everychoice of a constantk> 0, you can find a constantasuch that the inequality f(x) < 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 `<=`

versus `<`

.

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^2 ∈ O(x^2)
- x^2 ∈ O(x^2 + x)
- x^2 ∈ O(200 * x^2)

The following are true for little-o:

- x^2 ∈ o(x^3)
- x^2 ∈ o(x!)
- ln(x) ∈ o(x)

Note that if f ∈ o(g), this implies f ∈ O(g). e.g. x^2 ∈ o(x^3) so it is also true that x^2 ∈ O(x^3), (again, think of O as `<=`

and o as `<`

)

Big-O is to Little-o as `<=`

is to `<`

. Big-O is an inclusive upper bound, and Little-o is a strict upper bound.

For example, a function that grows linearly:

- Is
`O(n^2)`

,`o(n^2)`

and`O(n)`

- Is not
`o(n)`

,`O(lg n)`

or`o(lg n)`

Analogously, the number `1`

:

- Is
`<= 2`

,`< 2`

and`<= 1`

- Is not
`< 1`

,`<= 0`

or`< 0`

Here's a table, showing the general idea:

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 `n^O(1) = P`

.

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^2), 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/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. :)

Similar Questions

What is the difference between, RewriteRule ^(.+)$ /myproject/index.php/$1 [L,QSA] and RewriteRule ^(.*)$ /myproject/index.php/$1 [L]

I have recently jumped into the world of jQuery. I saw the methods find() and filter() but can not figure out the difference between the two. What exactly is the difference between the two?

What is the difference between px and em?

What is difference between LoadedpivotItem and LoadingPivotItem ? Or there is any link where u can get all the pivot Events documentation ?

What the difference between CRC and checksum?

This question already has an answer here: What does python file extensions, .pyc .pyd .pyo stand for? 2 answers What is the difference (if any) between .pyc and .py[cod] notation in ignorin

I want to know the exact difference between the dll and exe file.

This question already has an answer here: Difference between knockout View Models declared as object literals vs functions 2 answers Literal notation VS. constructor to create objects in JavaScr

Can someone please explain the exact difference between Σ* and L* , where L is a language and Σ is alphabet of the language L ? Thanks

I've been searching the difference between those two but I couldn't find actually what I want. I need learn the difference when using LINQ To SQL but they all gave me standard array examples. Can som

What is the difference between @mock and @InjectMocks in Mockito framework?

in the yii framework what is the difference between radioButtonList and activeRadioButtonList?

i want know difference between Lambda expression and Action.?

What is difference between the following two function definitions? A 2D array is being passed as parameter. void fun(int a[][3]) { //do some task } void fun(int (*a)[3]) { //do some task }

Just wanted to know if someone can explain the difference between these two conditionals: if ( !object ) if ( object == null ) where object is an instance of a user-defined class. I'm sure that these

Is there a difference between classOf[String].isInstance(42) and 42.isInstanceOf[String] ? If yes, can you explain ?

int array[10]; int main (){ int *data_ptr; int value; data_ptr = &array[0]; value = *data_ptr++; value = *++data_ptr; value = ++*data_ptr; return 0; } Which is the difference between each assignm

What is the difference between iostream and iostream.h?

Can any one explain the difference between Scroll View and List View? When to use which one? And which one is more efficient? Thanks

I've misplaced += with =+ one to many times, and I think I keep forgetting because I don't know the difference between these two, only that one gives me the value I expect it to, and the other does no

Is there any difference between servlet-path and servlet-class tags when you define a servlet mapping under web.xml? <servlet> <servlet-name>register</servlet-name> <servlet-path&

I'm a little bit confused, can somebody please explain the main difference between those types of containers: map list set array thanks in advanca(I'm asking about C++)

I want to know what is the difference between fgets() and scanf(). I am using C as my platform.

I am creating an array in C of known size that doesn't ever change. What is the difference between the following two initializers? 1. GLuint boxArray[36]; for (GLuint i=0; i<36; i++) { boxArray[i]

This question already has an answer here: Literal notation VS. constructor to create objects in JavaScript 2 answers I'm just working through Codeacademy, and they show you have to write both.

Possible Duplicate: What are the differences between using int[][] and int[,]? I just came across this notation: int[,] Whenever i needed a matrix I used: int[][] What is the difference? When to u

I am new to php and would like to know if there are any differences between these server tags : <?php ?> and <? ?>

if I'm writing an XSLT, is there any difference between <xsl:template match=/*> <xsl:element name=a><xsl:apply-templates/></xsl:element> </xsl:template> and <xsl

I was trying to solve the problem on spoj but my answer is not accepting giving wrong answer i want to know difference between these two chunks of code. Spoj accepting this public class Test { public

I am trying to understand the difference between .Notation and [] notation. In my problem below when I use if (object[key] === true) I get the correct answer. When I use if (object.key === true) it do

I found a lot of similar questions Difference between Hibernate library and Hibernate JPA library What's the difference between JPA and Hibernate? similarity and difference between jpa and hibernate

Does someone know the difference between Dispatcher.BeginInvoke(DispatcherPriority.Background, new ThreadStart(() => { and Dispatcher.BeginInvoke(DispatcherPriority.Background, new Action(() =&g

can you explain me which is the difference between <xsl:template match=/*> and <xsl:template match=*> and <xsl:template match=/> Look at the match rule :) Thank you so much

What is the difference between passing-by-reference and using the C pointer notation? void some_function(some_type& param) and void some_function(some_type *param) Thanks

What is the difference between break and continue in PHP?

What is the difference between socket programming and Http programming? can anyone help please?

Does the double line in the following ER diagrams means total participation or recursive relation? Could anyone tell me the notation difference for both?

What is the difference between setVisibility(View.GONE) and setAlpha(0f)?

How to find the difference between two dates?

Is there any difference in performance - or otherwise - between: ptr->a(); and (*ptr).a(); ?

Can some body tell me the difference between timestamp(0) and timestamp(6) in Teradata

I know the performance difference between the following two Include directive (<%@ include file=test.jsp %>): This includes the contents of the file during the compilation phase—i.e., when th

Can anyone tell me the difference between break and continue statements?

I am taking two NSDates by using date time picker. Now I want to count the number of days between these two NSDates. How can I find the difference between two NSDates. please give me some solution. Th

What is the difference between ToolsVersion and TargetFrameworkVersion? <Project DefaultTargets=Build ToolsVersion=4.0 xmlns=http://schemas.microsoft.com/developer/msbuild/2003> <Proper

what is the difference between this regular expressions are the replaceable? ((?:[^\])*) ([^\]*) background to this question: The javascript WYSIWYG editor (tinymce) fails to parse my html code in

Recently I am studying operating system..I just wanna know: What’s the difference between a system call (like write()) and a standard library function (like printf())?

What is the difference, in cmake, between something like: set(any_new_var ${old_var}) and set(any_new_var ${old_var}) Any important difference? When have I to use one or the other form? For exampl

I have extracted following difference between inheritance and composition. I wanted to know what does delay of creation of back end object mean? Please find below difference. Composition allows you to

I have the following questions regarding MBean and MXBean: What is the difference between MBean and MXBean? What are the use cases for MBean and MXBean?