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.