Big Oh notation is used in computer science to decribe the complexity of an algorithm in terms of time and space (memory). Big Oh notation describes the **worst case scenario** of what happens when an algorithm is run with N values and is really only useful when talking about large sets of data.

constant |
logarithmic |
linear |
quadratic |
cubic |
||
---|---|---|---|---|---|---|

n | O(1) | O(log N) | O(N) | O(N log N) | O(N^{2}) |
O(N^{3}) |

1 | 1 | 1 | 1 | 1 | 1 | 1 |

2 | 1 | 1 | 2 | 2 | 4 | 8 |

4 | 1 | 2 | 4 | 8 | 16 | 64 |

8 | 1 | 3 | 8 | 24 | 64 | 512 |

16 | 1 | 4 | 16 | 64 | 256 | 4,096 |

1,024 | 1 | 10 | 1,024 | 10,240 | 1,048,576 | 1,073,741,824 |

1,048,576 | 1 | 20 | 1,048,576 | 20,971,520 | 10^{12} |
10^{16} |

*Source: table source here also big thanks to Dean who made the graph for me 🙂*

### Explanation

**O(1)** = irrespective of changing the size of the input, time stays the same

**O(N)** = as you increase the size of input, the time taken to complete operations scales linearly with that size

**O(log N) = **growth curve that peaks at the beginning and slowly flattens out as the size of the data sets increase

**O(****N ^{2}**

**) =**growth will double with each additional element in the input

**Java Example for** **O(1):**

public static boolean isArrayOver100(String[] args) { if (args.length > 100) return true; return false; }

**Java Example for O(N):**

public static boolean contains(String[] args, String value) { for (int i = 0; i < args.length; i++) { if (args[i] == value) return true; } return false; }

**Java Example for O(log N):**

public static int binarySearch(int[] toSearch, int key) { int fromIndex = 0; int toIndex = toSearch.length - 1; while (fromIndex < toIndex) { int midIndex = (toIndex - fromIndex / 2) + fromIndex; int midValue = toSearch[midIndex]; if (key > midValue) { fromIndex = midIndex++; } else if (key < midValue) { toIndex = midIndex - 1; } else { return midIndex; } } return -1; }

See my other post on binary search here.

**Java Exmaple O(****N ^{2}**

**)**

public static boolean containsDuplicates(String[] args) { for (int i = 0; i < args.length; i++) { for (int j = 0; j < args.length; j++) { if (i == j) break; if (args[i] == args[j]) return true; } } return false; }

I took this post as my inspiration as I found it to be a great introduction but have instead used java for the code examples.

its looks like magic,what are the costs and the n time each java statement makes.thank you for your anticipated reply/answer.

hey!I observed the previous post(your inspiration)..but that was also written in Java.It had bool return type and String as a data type.

But i think your post was as good as your inspiration..The graphs did help me a lot.:-)

Thanks!

Hey, I came here also from the aforementioned inspiration link, but i gotta say, that graph was really what I needed to tie it all together. Thanks for the effort!

(Also I don’t speak Java very fluently and your examples were perfectly clear to me, so good work there as well)

Thanks so much for your feedback – glad you liked the graphs!

I have a question for you. Do you know of a tutorial for computing Time Complexity mathematically?

Sorry – I’m not sure of any.

Just one minor correction: Your entry for “O(N^2) = growth will double with each additional element in the input” is confusing O(N^2) with O(2^N). The description is correct for the latter. For the former, you would say that time complexity increases proportional to the square of the size of the input set.

Good post. One minor correction

The value under the cubic column for 1,048,576 should be 10 to the power 18, not 10 to the power 16.

Exponent 16 should be changed to 18.

Thanks for the interesting post. I found it through

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

which was linked on Twitter by some coders I work with.

I also blogged about algorithms basics, just today!

http://apprenticecoder.wordpress.com/2011/09/25/algorithm-basics-avoid-nested-loops-and-divide-and-conquer-often/

Have a nice day!

Olja

Thanks you for this post !

Just a detail but you should use “equals” when compare 2 strings.

For example: if (args[i] == value) should be if( args[i].equals(value))

The topic has been explained in a very lucid manner. Thank you very much for making me understand the concept. It would be of great help to me as I am having my examination tomorrow.