Big O Notation

Posted by

Aka Time Complexity

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

O(1) Constant time : random access in array

O(n) Linear time : delete value linked list

Common Runtimes

NameDescription
Constant time – O(1)Same amount of time, regardless of number of elementsRandom 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 linearlyLooping an array/list
Quasiliner -O(n log n)Every element has to be compared with every other element. Lost of comparisonsSort Algorithms
Quadratic – O(n2)2,4,8,16,32,64 Increasing quadraticallyNested loops
Exponential – O (2^n)RecursionFibonacci 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
                }
            }
        }
        
    }

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.