This is completely made-up and a very forced example, but imagine two different algorithms with loops like below, where they both call some inner function (DoAlgorithmInner1/DoAlgorithmInner2) that we assume are both of equal cost.

for( i=0; i < n; ++i )
  for( j=0; j < 100; ++j )
    DoAlgorithmInner1( i, j )

for( i=0; i < n; ++i )
  for( j=0; j < n; ++j )
    DoAlgorithmInner2( i, j );

The first is O(n*100), which is O(n*constant), which is just O(n).
The second is O(n2).

Say that n is only 10 -- the first one calls the inner function 10*100 times, the second calls it 10*10 times.
Say that n is 10000 -- the first one calls the inner function 10000*100 times, the second calls it 10000*10000 times.

So for any case where n is less than 100, the n^2 algorithm actually does less work.


For a real world example -- try implementing a comparison sort, like quicksort, which is O(n log n) and also a radix sort, which is O(n).
The constants, which are removed from the big-O analysis are actually very high with the radix sort, which makes it behave like the above example.
e.g. n*1000 might be more expensive than n*n*10.

Nice example and clear explaination

if something ( A ) is in the big Oh of something else ( B ), ignoring everything but the n's in each sides

B will eventually be larger than A ( from any n towards infinity ).

The main purpose of this is to check the efficiency of a piece of code

https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities

^ this is probably all you need to know

also Big Oh is for the worst case

basic example:

if you loop through all n elements in an array to find a specific element, worst case scenario you will go through all n elements, so we say the code will run in the big oh of n.

Big Oh notation gives a worst case estimate on how often data needs to be inspected to run the algorithm it is defined for. Little o gives the lower bound and capital theta gives the lower and upper bounds in one function.

In CS however we are usually only interested in the worst case scenario as it is better to optimise the algorithm for that case.

if something ( A ) is in the big Oh of something else ( B ), ignoring everything but the n's in each sides

B will eventually be larger than A ( from any n towards infinity ).

also Big Oh is for the worst case

basic example:

if you loop through all n elements in an array to find a specific element, worst case scenario you will go through all n elements, so we say the code will run in the big oh of n.

Big oh is worse case only, it expresses the upper bound growth function on the algorithm not the average case. Even in an unsorted array a binary search will at worst case need n log(n) accesses to find an element that is at least equal to the one you specified, given that the value you are searching for should be in that array. Even in that case you could find an element that is the one your are looking for in the first go and that could happen 90% of the time. Big oh says nothing about the average case it only mentions something about the worst case behaviour of your algorithm.

quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Quote

name='Wikipedia']
quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Right there, you see a use of big-O notation for the average case.

EDIT: And a bunch of examples in one place (a whole table, actually): http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Tragically you gave an example of incorrect usages of Big-O notation.

Big-O notation is only for worst case growth of a function. Please refer to the formal definition also provided on wikipedia or any number of math texts. (Formal definition on wikipedia as I can't link to math texts: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition)

Now - that doesn't mean that the Big-O for a particular function can't be the same as one or even all of the 5 Bachmann-Landu notations. Consider the very simple case of an algorithm that goes through a list of n numbers and adds 1 to each number. That would take n operations exactly - which means its worst case is n, its average case is n, and its best case is also n.

If you read the paragraph just above the table you mentioned the author states:

The run time and the memory of algorithms could be measured using various notations like theta, omega, Big-O, small-o, etc. The memory and the run times below are applicable for all the 5 notations.

Please see the following for an explanation of the other notations used: http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations

Outside of theoretical CS - you probably won't be seeing the other notations, as the common practice seems to be simply to abuse Big-O and use it everywhere even if it is an incorrect usage.

Quote

name='Wikipedia']
quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items. In the worst case, it makes O(n2) comparisons, though this behavior is rare.

Right there, you see a use of big-O notation for the average case.

EDIT: And a bunch of examples in one place (a whole table, actually): http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Tragically you gave an example of incorrect usages of Big-O notation.

Big-O notation is only for worst case growth of a function. Please refer to the formal definition also provided on wikipedia or any number of math texts. (Formal definition on wikipedia as I can't link to math texts: http://en.wikipedia.org/wiki/Big_O_notation#Formal_definition)

Now - that doesn't mean that the Big-O for a particular function can't be the same as one or even all of the 5 Bachmann-Landu notations. Consider the very simple case of an algorithm that goes through a list of n numbers and adds 1 to each number. That would take n operations exactly - which means its worst case is n, its average case is n, and its best case is also n.

If you read the paragraph just above the table you mentioned the author states:

>The run time and the memory of algorithms could be measured using various notations like theta, omega, Big-O, small-o, etc. The memory and the run times below are applicable for all the 5 notations.

Please see the following for an explanation of the other notations used: http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations

Outside of theoretical CS - you probably won't be seeing the other notations, as the common practice seems to be simply to abuse Big-O and use it everywhere even if it is an incorrect usage.

If anyone is interested in hearing what's wrong with that post, please ask and I will explain. Otherwise, I won't waste my time.