What is Big O Notation? [duplicate]

Question

Possible Duplicate:
Plain English explanation of Big O

I know Big O notation is used to assess how efficient an algorithm is, but I do not understand how you read Big O notation or what exactly how efficient an algorithm is. Can somebody perhaps explain the basics of Big O notation? Thanks.

Answer 1

What is a plain English explanation of "Big O" notation? is a good explanation of what Big-O notation is and how to use it.

Answer 2

This page looks to explain it pretty clearly to me.

Essentially it's a convenient way of quickly and accurately assessing the performance characteristics of an algorithm. Be it how quickly in the worst case or average case the algorithm runs. How much space in the worst or average case it uses. Sometimes more useful is how an algorithm performs on a number of items, this is known as amortized analysis.

The fundamental characteristic of the notation is that it leaves out terms that become irrelevant as n gets large. For example as n gets large n^2 + 2n the 2n becomes irrelevant. This would be O(n^2).

Answer 3

Big O Notation describes the limiting behavior of a function.

For computer science, typically, you use this to show how an algorithm scales well as you get larger sets of data. For example, lookups in collections typically vary, and are described using Big-O notation, based on the type of collection. A Dictionary<T,U> in the .NET Framework has an Item property which is documented as follows:

Getting or setting the value of this property approaches an O(1) operation

That basically says, no matter how many items you add to the collection, getting an item out will be done in constant time. A List<T>, on the other hand, describes its Contains method as follows:

This method performs a linear search; therefore, this method is an O(n) operation, where n is Count.

This basically says the algorithm will get slower, in linear time, as you add more items. If you put in 1000 items, it will take approximately 10x as long, on average, as a list containing 100 items, etc.