Big O Notation

1. Big O : It is a complexity that is going to be less or equal to the worst case.

2. Big Omega : It is a complexity that is going to be at least more than the best case.

3. Big Theta : It is a complexity that is within bounds of the worst and the best cases.

Runtime complexities:

1. O(1) : Constant. Accessing a specific element in array

int[] arr = {1, 5, 3, 9, 4};
int el = arr[3];

2. O(N) : Linear. Loop through array elements

int[] arr = {1, 5, 3, 9, 4};
for(int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

3. O(Log N) : Logarithmic. Find an element in stored array 

int[] arr = {1, 5, 3, 9, 4, 2, 8, 6};
for (int i = 0; i < arr.length; i += 3) {
    System.out.println(arr[i]);
}

Another example is Binary search.

4. O(N^2) : Quadratic. Looking at every index in the array twice.

int[] arr = {1, 5, 3, 9, 4, 2, 8, 6};
for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr.length; j++) {
        System.out.println(arr[j]);
    }
}

5. O(2^N) : Exponential. Double recursion in Fibonacci.

public int fibonacci(int n) {
    if (n == 0 || n == 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}