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

Binary search is a well-known search algorithm that works on an already-sorted input. The basic idea is to successively eliminate half of the remaining search space at each step till either the target is found or there's no more search space left.
Binary search is recursive in nature but can also be implemented iteratively. Below is the recursive implementation of binary search.

class Demonstration {
    public static void main( String args[] ) {
        int[] input = new int[] { 1, 3, 4, 6, 7, 101, 1009 };
        System.out.println(binarySearch(0, input.length - 1, 1009, input));
        System.out.println(binarySearch(0, input.length - 1, -1009, input));
        System.out.println(binarySearch(0, input.length - 1, 5, input));
        System.out.println(binarySearch(0, input.length - 1, 6, input));      
    }

    /**
     * start and end are inclusive indices
     *
     * @param start
     * @param end
     * @param target
     * @param input
     * @return
     */
    public static boolean binarySearch(int start, int end, int target, int[] input) {

        if (start > end) {
            return false;
        }

        int mid = (start + end) / 2;

        if (input[mid] == target) {
            return true;
        } else if (input[mid] > target) {
            return binarySearch(start, mid - 1, target, input);
        } else {
            return binarySearch(mid + 1, end, target, input);
        }
    }  
  
}

<h2>Recurrence Equation</h2>
The recurrence equation for binary search is given below: 

>$$Running\:Time = Cost \:to\:divide\:into\:p\:subproblems + p * Cost\:to\:solve\:each\:of\:the\:p\:problems + Cost\:to\:merge\:all\:p\:problems$$
>
>$$T(n)=O(1)+2*T\frac{n}{2} + O(1)$$
>$$T(n)=T(\frac{n}{2})$$

The running time of binary search is the solution to the above recurrence. Note that we divide the original problem into 2 subproblems. Division is just an arithmetic operation that takes constant time and has no relation to the size of the input. We don't have to combine the solution of the subproblems, as we eliminate one half of the search space at each recursion.

The recursion tree appears below.

This chapter details the reasoning behind binary search's time complexity

Basics

Formal Analysis Tools

Recursive

Data-Structures

Amortized Analysis

Probabilistic Analysis

Complexity Theory

The End

Binary Search - Recursive Implementation