The ultimate guide to Big-O notation for coding interviews, developed by FAANG engineers. Learn algorithm complexity in simple terms and get interview-ready in just a few hours.

This course is intended for professionals that lack formal education in computer science, and that are in search of a simple and practical guide to algorithmic complexity. The course explains the concepts in layman's terms, and teaches how to reason about the complexity of algorithms without requiring one to have an extensive mathematical skillset. This course can also be handy for revising complexity concepts or Big-O analysis before interviews. Finally, the content also scratches the surface of some advanced analysis topics to provide a more encompassing image of the complexity theory.

Big-O Notation For Coding Interviews and Beyond

<h2>The Interview Room</h2>
<p>You're in an interview room, and you've just completed white-boarding the interviewer's question. Inside, you feel ecstatic; It's your dream company and you nailed the question. However, just when you think the coast is clear, the interviewer follows up with a question on the <i>time</i> or <i>space</i> complexity of your solution. The blank drawn across your face gives away your ineptness at analyzing algorithm complexity in space or time. In this common interview situation, most computer science graduates are still able to muster up a reasonable answer. For candidates lacking the formal education, however, reasoning about algorithms in terms of the <b><i>big Oh</i></b> notation becomes a <b><i>big uh oh!</b></i>.</p>


<p>The intended readership of this course includes folks who are graduates of boot-camps, career-switchers into programming jobs or just established industry veterans who want a quick revision on the topic of complexity theory. The course uses layman's terms to describe the concepts commonly used in the industry while intentionally avoiding the intricate mathematical gymnastics often involved in analyzing algorithms so that the subject material is comprehensible for readers at all skill levels. At the same time, this course may not deliver great value to individuals who already have a firm grasp of algorithms and data-structures or to those that hold a degree in computer science.</p>

<h2>Why does complexity matter?</h2>
<p>If you are working on a class assignment or a customer application with a few dozen users, you can take the liberty to ignore the space and time complexity of your solution. However, the moment you step into the professional world and write software with strict SLAs (service level agreements) or for millions of users, your choice of algorithm and data-structures starts to matter. A well designed and thought out software will scale elegantly and set itself apart from poorly written competitors.</p>
<p>Usually, the <i>101</i> example used to teach complexity is sorting of integers. Below are three example programs that sort integers using different sorting algorithms.</p>

import java.util.Random;
class Demonstration {

    static int SIZE = 10000;
    static Random random = new Random(System.currentTimeMillis());
    static int[] input = new int[SIZE];
  
    public static void main( String args[] ) {
        createTestData();
        long start = System.currentTimeMillis();
        bubbleSort(input);
        long end = System.currentTimeMillis();
        System.out.println("Time taken = " + (end - start));
    }

    static void bubbleSort(int[] input) {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE - 1; j++) {
                if (input[j] > input[j + 1]) {
                    int tmp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = tmp;
                }
            }
        }
    }

    static void createTestData() {
        for (int i = 0; i < SIZE; i++) {
            input[i] = random.nextInt(10000);
        }
    }  
}

import java.util.Random;
class Demonstration {

    static int SIZE = 5000;
    static Random random = new Random(System.currentTimeMillis());
    static int[] input = new int[SIZE];
    static int[] scratch = new int[SIZE];  
  
    public static void main( String args[] ) {
        createTestData();
        long start = System.currentTimeMillis();
        mergeSort(0, input.length - 1, input);
        long end = System.currentTimeMillis();
        System.out.println("Time taken = " + (end - start));
    }

    static void mergeSort(int start, int end, int[] input) {

        if (start == end) {
            return;
        }

        int mid = (start + end) / 2;

        // sort first half
        mergeSort(start, mid, input);

        // sort second half
        mergeSort(mid + 1, end, input);

        // merge the two sorted arrays
        int i = start;
        int j = mid + 1;
        int k;

        for (k = start; k <= end; k++) {
            scratch[k] = input[k];
        }

        k = start;
        while (k <= end) {

            if (i <= mid && j <= end) {
                input[k] = Math.min(scratch[i], scratch[j]);

                if (input[k] == scratch[i]) {
                    i++;
                } else {
                    j++;
                }
            } else if (i <= mid && j > end) {
                input[k] = scratch[i];
                i++;
            } else {
                input[k] = scratch[j];
                j++;
            }
            k++;
        }
    }

    static void createTestData() {
        for (int i = 0; i < SIZE; i++) {
            input[i] = random.nextInt(1000);
        }
    }  
}

import java.util.Random;
import java.util.Arrays;

class Demonstration {

    static int SIZE = 5000;
    static Random random = new Random(System.currentTimeMillis());
    static int[] input = new int[SIZE];
  
    public static void main( String args[] ) {
        createTestData();
        long start = System.currentTimeMillis();
        Arrays.sort(input);
        long end = System.currentTimeMillis();
        System.out.println("Time taken = " + (end - start));
    }

    static void createTestData() {
        for (int i = 0; i < SIZE; i++) {
            input[i] = random.nextInt(10000);
        }
    }  
}

<p>The code implementations above run on datasets of 5000 elements. Below are some crude tests (run on a Macbook) for the three algorithms. All times are in milliseconds</p>

<table>
<tr><th>Size</th><th>Bubble Sort</th><th>Merge Sort</th><th>Java's util.Arrays.sort</th></tr>
<tr><td>5000</td><td>90</td><td>9</td><td>4</td></tr>
<tr><td>10000</td><td>299</td><td>15</td><td>17</td></tr>
<tr><td>100000</td><td>24719</td><td>26</td><td>33</td></tr>
<tr><td>1000000</td><td>2474482</td><td>150</td><td>113</td></tr>
</table>

<p>The results tabulated above should provide plenty of motivation for software developers to increase their understanding of algorithmic performance. Bubble sort progressively degrades in performance as the input size increases, whereas the other two algorithms perform roughly the same. We'll have more to say about their performances in the next chapter.</p>

<h2>Time & Space</h2>
<p>The astute reader would notice the use of an additional array in the merge sort code, named <i>scratch</i> array. This is the classic trade-off in the computer science realm. Throwing more space at a problem allows us to bring down the execution time, and vice versa. Generally, time and space have an inversely proportional relationship with each other; if space increases then execution time decreases, and if execution time increases then space decreases.</p>

This chapter lays the groundwork for the material covered in the course and sets out the expectations for the readers.

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Introduction