Big O Notation

Aka Time Complexity

• The efficiency of your algorithm
• Used to describe runtime characteristics of our data structures and algorithms

Common Runtimes

Name	Description
Constant time – O(1)	Same amount of time, regardless of number of elements	Random access array
Logarithmic – O(log n)	When doubling the number of elements doesn’t double the time (binary trees)	Search algorithms
Linear – O(n)	Adding element increases runtime linearly	Looping an array/list
Quasiliner -O(n log n)	Every element has to be compared with every other element. Lost of comparisons	Sort Algorithms
Quadratic – O(n2)	2,4,8,16,32,64 Increasing quadratically	Nested loops
Exponential – O (2^n)	Recursion	Fibonacci Series

Examples

   // O(n)
    @Test
    void testO_2n() {
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            //...
        }
        for (int i = 0; i < array.length; i++) {
            //...
        }
    }

    // O(n*m)
    void testO_2() {
        int[] array1 = new int[10];
        int[] array2 = new int[10];
        for (int i = 0; i < array1.length; i++) {
            //...
            for (int j = 0; j < array2.length; j++) {
                //...
            }
        }
        
    }

    // O(n^2)
    @Test
    void test3() {
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            //...
            for (int j = 0; i < array.length; j++) {
                if(array[i] < array[j]) {
                    // do it
                }
            }
        }
        
    }