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

Rules of Thumbs

References