Big O Notations
Intent
Problem
Example
Look at this simple code to check whether x
is inside an array or not.
boolean contains(int[] array, int x) {
for (int i = 0; i < array.length; i++) {
if (array[i] == x) {
return true;
}
}
return false;
}
Runtime complexity:
O(n)
The runtime complexity for about sample would be O(n)
or Linear where n
is the size of the array. Lets take a look for another example.
The function will using two loops in order to make a pair.
void printPairs(int[] array) {
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length; j++) {
System.out.println(Integer.toString(array[i]).concat(Integer.toString(a[j])));
}
}
}
Runtime complexity:
O(n2)
N squared, because it has an element in the array so it has n