# An Intro to Big Oh Notation with Java

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(N2) O(N3)
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 1012 1016

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(N2) = 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(N2)

```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.

Advertisements

## 14 thoughts on “An Intro to Big Oh Notation with Java”

1. Pingback: Big O notation - Java Forums
2. illy my illy says:

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

3. soumyadip says:

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.:-)

4. SM says:

Thanks!

5. mediapathic says:

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)

• nerdgerl says:

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

6. LdapPro says:

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

• nerdgerl says:

Sorry – I’m not sure of any.

7. shiphorns says:

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.

8. Logan says:

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.

9. Pingback: Algorithm basics – avoid nested loops and divide and conquer often | Apprenticecoder's Blog
10. apprenticecoder says:

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

11. dalf says:

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))

12. Sidharth Sahoo says:

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.