This means that the method you use to arrive at the same solution may differ from mine, but we should both get the same result.

Because there are various ways to solve a problem, there must be a way to evaluate these solutions or algorithms in terms of performance and efficiency (the time it will take for your algorithm to run/execute and the total amount of memory it will consume).

This is critical for programmers to ensure that their applications run properly and to help them write clean code.

This is where Big O Notation enters the picture. Big O Notation is a metric for determining the efficiency of an algorithm. It allows you to estimate how long your code will run on different sets of inputs and measure how effectively your code scales as the size of your input increases.

What is Big O?

Big O, also known as Big O notation, represents an algorithm's worst-case complexity. It uses algebraic terms to describe the complexity of an algorithm.

Big O defines the runtime required to execute an algorithm by identifying how the performance of your algorithm will change as the input size grows. But it does not tell you how fast your algorithm's runtime is.

Big O notation measures the efficiency and performance of your algorithm using time and space complexity.

What is Time and Space Complexity?

One major underlying factor affecting your program's performance and efficiency is the hardware, OS, and CPU you use.

But you don't consider this when you analyze an algorithm's performance. Instead, the time and space complexity as a function of the input's size are what matters.

An algorithm's time complexity specifies how long it will take to execute an algorithm as a function of its input size. Similarly, an algorithm's space complexity specifies the total amount of space or memory required to execute an algorithm as a function of the size of the input.

We will be focusing on time complexity in this guide. This will be an in-depth cheatsheet to help you understand how to calculate the time complexity for any algorithm.

Why is time complexity a function of its input size?

To perfectly grasp the concept of "as a function of input size," imagine you have an algorithm that computes the sum of numbers based on your input. If your input is 4, it will add 1+2+3+4 to output 10; if your input is 5, it will output 15 (meaning 1+2+3+4+5).

const calculateSum = (input) => {
  let sum = 0;
  for (let i = 0; i <= input; i++) {
    sum += i;
  }
  return sum;
};

In the code above, we have three statements:

Looking at the image above, we only have three statements. Still, because there is a loop, the second statement will be executed based on the input size, so if the input is four, the second statement (statement 2) will be executed four times, meaning the entire algorithm will run six (4 + 2) times.

In plain terms, the algorithm will run input + 2 times, where input can be any number. This shows that it's expressed in terms of the input. In other words, it is a function of the input size.

In Big O, there are six major types of complexities (time and space):

• Constant: O(1)

• Linear time: O(n)

• Logarithmic time: O(n log n)

• Quadratic time: O(n^2)

• Exponential time: O(2^n)

• Factorial time: O(n!)

Before we look at examples for each time complexity, let's understand the Big O time complexity chart.

Big O Complexity Chart

The Big O chart, also known as the Big O graph, is an asymptotic notation used to express the complexity of an algorithm or its performance as a function of input size.

This helps programmers identify and fully understand the worst-case scenario and the execution time or memory required by an algorithm.

The following graph illustrates Big O complexity:

The Big O chart above shows that O(1), which stands for constant time complexity, is the best. This implies that your algorithm processes only one statement without any iteration. Then there's O(log n), which is good, and others like it, as shown below:

• O(1) - Excellent/Best

• O(log n) - Good

• O(n) - Fair

• O(n log n) - Bad

• O(n^2), O(2^n) and O(n!) - Horrible/Worst

You now understand the various time complexities, and you can recognize the best, good, and fair ones, as well as the bad and worst ones (always avoid the bad and worst time complexity).

The next question that comes to mind is how you know which algorithm has which time complexity, given that this is meant to be a cheatsheet 😂.

• When your calculation is not dependent on the input size, it is a constant time complexity (O(1)).

• When the input size is reduced by half, maybe when iterating, handling recursion, or whatsoever, it is a logarithmic time complexity (O(log n)).

• When you have a single loop within your algorithm, it is linear time complexity (O(n)).

• When you have nested loops within your algorithm, meaning a loop in a loop, it is quadratic time complexity (O(n^2)).

• When the growth rate doubles with each addition to the input, it is exponential time complexity (O2^n).

Let's begin by describing each time's complexity with examples. It's important to note that I'll use JavaScript in the examples in this guide, but the programming language isn't important as long as you understand the concept and each time complexity.

Big O Time Complexity Examples

Constant Time: O(1)

When your algorithm is not dependent on the input size n, it is said to have a constant time complexity with order O(1). This means that the run time will always be the same regardless of the input size.

For example, if an algorithm is to return the first element of an array. Even if the array has 1 million elements, the time complexity will be constant if you use this approach:

const firstElement = (array) => {
  return array[0];
};

let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12

The function above will require only one execution step, meaning the function is in constant time with time complexity O(1).

But as I said earlier, there are various ways to achieve a solution in programming. Another programmer might decide to first loop through the array before returning the first element:

const firstElement = (array) => {
  for (let i = 0; i < array.length; i++) {
    return array[0];
  }
};

let score = [12, 55, 67, 94, 22];
console.log(firstElement(score)); // 12

This is just an example – likely nobody would do this. But if there is a loop, this is no longer constant time but now linear time with the time complexity O(n).

Linear Time: O(n)

You get linear time complexity when the running time of an algorithm increases linearly with the size of the input. This means that when a function has an iteration that iterates over an input size of n, it is said to have a time complexity of order O(n).

For example, if an algorithm is to return the factorial of any inputted number. This means if you input 5 then you are to loop through and multiply 1 by 2 by 3 by 4 and by 5 and then output 120:

const calcFactorial = (n) => {
  let factorial = 1;
  for (let i = 2; i <= n; i++) {
    factorial = factorial * i;
  }
  return factorial;
};

console.log(calcFactorial(5)); // 120

The fact that the runtime depends on the input size means that the time complexity is linear with the order O(n).

Logarithm Time: O(log n)

This is similar to linear time complexity, except that the runtime does not depend on the input size but rather on half the input size. When the input size decreases on each iteration or step, an algorithm is said to have logarithmic time complexity.

This method is the second best because your program runs for half the input size rather than the full size. After all, the input size decreases with each iteration.

A great example is binary search functions, which divide your sorted array based on the target value.

For example, suppose you use a binary search algorithm to find the index of a given element in an array:

const binarySearch = (array, target) => {
  let firstIndex = 0;
  let lastIndex = array.length - 1;
  while (firstIndex <= lastIndex) {
    let middleIndex = Math.floor((firstIndex + lastIndex) / 2);

    if (array[middleIndex] === target) {
      return middleIndex;
    }

    if (array[middleIndex] > target) {
      lastIndex = middleIndex - 1;
    } else {
      firstIndex = middleIndex + 1;
    }
  }
  return -1;
};

let score = [12, 22, 45, 67, 96];
console.log(binarySearch(score, 96));

In the code above, since it is a binary search, you first get the middle index of your array, compare it to the target value, and return the middle index if it is equal. Otherwise, you must check if the target value is greater or less than the middle value to adjust the first and last index, reducing the input size by half.

Because for every iteration the input size reduces by half, the time complexity is logarithmic with the order O(log n).

Quadratic Time: O(n^2)

When you perform nested iteration, meaning having a loop in a loop, the time complexity is quadratic, which is horrible.

A perfect way to explain this would be if you have an array with n items. The outer loop will run n times, and the inner loop will run n times for each iteration of the outer loop, which will give total n^2 prints. If the array has ten items, ten will print 100 times (10^2).

Here is an example by Jared Nielsen, where you compare each element in an array to output the index when two elements are similar:

const matchElements = (array) => {
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length; j++) {
      if (i !== j && array[i] === array[j]) {
        return `Match found at ${i} and ${j}`;
      }
    }
  }
  return "No matches found 😞";
};

const fruit = ["🍓", "🍐", "🍊", "🍌", "🍍", "🍑", "🍎", "🍈", "🍊", "🍇"];
console.log(matchElements(fruit)); // "Match found at 2 and 8"

In the example above, there is a nested loop, meaning that the time complexity is quadratic with the order O(n^2).

Exponential Time: O(2^n)

You get exponential time complexity when the growth rate doubles with each addition to the input (n), often iterating through all subsets of the input elements. Any time an input unit increases by 1, the number of operations executed is doubled.

The recursive Fibonacci sequence is a good example. Assume you're given a number and want to find the nth element of the Fibonacci sequence.

The Fibonacci sequence is a mathematical sequence in which each number is the sum of the two preceding numbers, where 0 and 1 are the first two numbers. The third number in the sequence is 1, the fourth is 2, the fifth is 3, and so on... (0, 1, 1, 2, 3, 5, 8, 13, …).

This means that if you pass in 6, then the 6th element in the Fibonacci sequence would be 8:

const recursiveFibonacci = (n) => {
  if (n < 2) {
    return n;
  }
  return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2);
};

console.log(recursiveFibonacci(6)); // 8

In the code above, the algorithm specifies a growth rate that doubles every time the input data set is added. This means the time complexity is exponential with an order O(2^n).

Wrapping Up

In this guide, you have learned what time complexity is all about, how performance is determined using the Big O notation, and the various time complexities that exists with examples.

You can learn more via freeCodeCamp's JavaScript Algorithms and Data Structures curriculum.

Happy learning!

You can access over 200 of my articles by visiting my website. You can also use the search field to see if I've written a specific article.

In this article, we'll learn how search algorithms work by looking at their implementations in Java and Python.

What is a Search Algorithm?

According to Wikipedia, a search algorithm is:

Any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.

Search algorithms are designed to check or retrieve an element from any data structure where that element is being stored. They search for a target (key) in the search space.

Types of Search Algorithms

In this post, we are going to discuss two important types of search algorithms:

1. Linear or Sequential Search

2. Binary Search

Let's discuss these two in detail with examples, code implementations, and time complexity analysis.

Linear or Sequential Search

This algorithm works by sequentially iterating through the whole array or list from one end until the target element is found. If the element is found, it returns its index, else -1.

Now let's look at an example and try to understand how it works:

arr = [2, 12, 15, 11, 7, 19, 45]

Suppose the target element we want to search is 7.

Approach for Linear or Sequential Search

• Start with index 0 and compare each element with the target

• If the target is found to be equal to the element, return its index

• If the target is not found, return -1

Code Implementation

Let's now look at how we'd implement this type of search algorithm in a couple different programming languages.

Linear or Sequential Search in Java

package algorithms.searching;

public class LinearSearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 11, 7, 19, 45};
        int target = 7;
        System.out.println(search(nums, target));

    }

    static int search(int[] nums, int target) {
        for (int index = 0; index < nums.length; index++) {
            if (nums[index] == target) {
                return index;
            }
        }
        return -1;
    }
}

Linear or Sequential Search in Python

def search(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

if __name__ == '__main__':
    nums = [2, 12, 15, 11, 7, 19, 45]
    target = 7
    print(search(nums, target))

Time Complexity Analysis

The Best Case occurs when the target element is the first element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

The Average Case: On average, the target element will be somewhere in the middle of the array. The number of comparisons, in this case, will be N/2. So, the time complexity will be O(N) (the constant being ignored).

The Worst Case occurs when the target element is the last element in the array or not in the array. In this case, we have to traverse the entire array, and so the number of comparisons will be N. So, the time complexity will be O(N).

Binary Search

This type of searching algorithm is used to find the position of a specific value contained in a sorted array. The binary search algorithm works on the principle of divide and conquer and it is considered the best searching algorithm because it's faster to run.

Now let's take a sorted array as an example and try to understand how it works:

arr = [2, 12, 15, 17, 27, 29, 45]

Suppose the target element to be searched is 17.

Approach for Binary Search

• Compare the target element with the middle element of the array.

• If the target element is greater than the middle element, then the search continues in the right half.

• Else if the target element is less than the middle value, the search continues in the left half.

• This process is repeated until the middle element is equal to the target element, or the target element is not in the array

• If the target element is found, its index is returned, else -1 is returned.

Code Implementation

Binary Search in Java

package algorithms.searching;

public class BinarySearch {
    public static void main(String[] args) {
        int[] nums = {2, 12, 15, 17, 27, 29, 45};
        int target = 17;
        System.out.println(search(nums, target));
    }

    static int search(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (nums[mid] > target)
                end = mid - 1;
            else if (nums[mid] < target)
                start = mid + 1;
            else
                return mid;
        }
        return -1;
    }
}

Binary Search in Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    while start <= end:
        mid = start + (end-start)//2


        if nums[mid] > target:
            end = mid-1
        elif nums[mid] < target:
            start = mid+1
        else:
            return mid

    return -1


if __name__ == '__main__':
    nums = [2, 12, 15, 17, 27, 29, 45]
    target = 17
    print(search(nums, target))

Time Complexity Analysis

The Best Case occurs when the target element is the middle element of the array. The number of comparisons, in this case, is 1. So, the time complexity is O(1).

The Average Case: On average, the target element will be somewhere in the array. So, the time complexity will be O(logN).

The Worst Case occurs when the target element is not in the list or it is away from the middle element. So, the time complexity will be O(logN).

How to Calculate Time Complexity:

Let's say the iteration in Binary Search terminates after k iterations.

At each iteration, the array is divided by half. So let’s say the length of array at any iteration is N.

At Iteration 1,

Length of array = N

At Iteration 2,

Length of array = N/2

At Iteration 3,

Length of array = (N/2)/2 = N/2^2

At Iteration k,

Length of array = N/2^k

Also, we know that after k divisions, the length of the array becomes 1: Length of array = N⁄₂^k = 1\=> N = 2^k

If we apply a log function on both sides: log₂ (N) = log₂ (2^k)\=> log₂ (N) = k log₂ (2)

As (log_a (a) = 1)
Therefore,=> k = log₂ (N)

So now we can see why the time complexity of Binary Search is log₂ (N).

You can also visualize the above two algorithms using the simple tool built by Dipesh Patil - Algorithms Visualizer.

Order-agnostic Binary Search

Suppose, we have to find a target element in a sorted array. We know that the array is sorted, but we don’t know if it’s sorted in ascending or descending order.

Approach for Order-agnostic Binary Search

The implementation is similar to binary search except that we need to identify whether the array is sorted in ascending order or descending order. This then lets us make the decision about whether to continue the search in the left half of the array or the right half of the array.

• We first compare the target with the middle element

• If the array is sorted in ascending order and the target is less than the middle element OR the array is sorted in descending order and the target is greater than the middle element, then we continue the search in the lower half of the array by setting end=mid-1.

• Otherwise, we perform the search in the upper half of the array by setting start=mid+1

The only thing we need to do is to figure out whether the array is sorted in ascending order or descending order. We can easily find this by comparing the first and last elements of the array.

if arr[0] < arr[arr.length-1]
    array is sorted in ascending order 
else
    array is sorted in descending order

Code Implementation

Order-agnostic Binary Search in Java

package algorithms.searching;

public class OrderAgnosticBinarySearch {
    public static void main(String[] args) {
        int[] nums1 = {-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99};
        int[] nums2 = {99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1};
        int target = -1;
        System.out.println(search(nums1, target));
        System.out.println(search(nums2, target));
    }

    static int search(int[] arr, int target) {
        int start = 0;
        int end = arr.length - 1;

        boolean isAscending = arr[start] < arr[end];

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (target == arr[mid])
                return mid;

            if (isAscending) {
                if (target < arr[mid]) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            } else {
                if (target < arr[mid]) {
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
        }
        return -1;
    }


}

Order-agnostic Binary Search in Python

def search(nums, target):
    start = 0
    end = len(nums)-1

    is_ascending = nums[start] < nums[end]

    while start <= end:
        mid = start + (end-start)//2

        if target == nums[mid]:
            return mid

        if is_ascending:
            if target < nums[mid]:
                end = mid-1
            else:
                start = mid+1
        else:
            if target < nums[mid]:
                start = mid+1
            else:
                end = mid-1

    return -1


if __name__ == '__main__':
    nums1 = [-1, 2, 4, 6, 7, 8, 12, 15, 19, 32, 45, 67, 99]
    nums2 = [99, 67, 45, 32, 19, 15, 12, 8, 7, 6, 4, 2, -1]
    target = -1
    print(search(nums1, target))
    print(search(nums2, target))

Time Complexity Analysis

There will be no change in the time complexity, so it will be the same as Binary Search.

Conclusion

In this article, we discussed two of the most important search algorithms along with their code implementations in Python and Java. We also looked at their time complexity analysis.

Thanks for reading!

Subscribe to my newsletter

We just published a course on the freeCodeCamp.org YouTube channel that will help you understand Big O Notation.

Georgio Tunson, aka selikapro, created this course. He does a great job explaining the complex concepts with diagrams and code.

Big O notation is a way to describe how long an algorithm takes to run or how much memory is used by an algorithm.

Here are the sections covered in this course:

• What Is Big O?
• O(n^2) Explanation
• O(n^3) Explanation
• O(log n) Explanation Recursive
• O(log n) Explanation Iterative
• O(log n) What Is Binary Search?
• O(log n) Coding Binary Search
• O(n log n) Explanation
• O(n log n) Coding Merge Sort
• O(n log n) Merge Sort Complexity Deep Dive
• O(2^n) Explanation With Fibonacci
• O(n!) Explanation
• Space Complexity & Common Mistakes

Watch the full course below or on the freeCodeCamp.org YouTube channel (2-hour watch).

Transcript

(autogenerated)

Big O notation is used to classify algorithms based on how fast they grow or decline.

It is very important to understand for many types of programming, Giorgio Thompson does a great job of breaking down big O notation in this course.

Hey, what's up everybody and welcome to my mini series on big O notation.

And this mini series, you'll learn everything that you need to know about big O notation and how you can use it to improve your ability to create efficient algorithms.

I'll use whiteboard illustrations to help you visualize and understand concepts followed by coding tutorials that you can follow along with to further solidify your grasp of the concepts will answer the question what is big O notation? And why is it useful? So what is big O notation? Big O notation is used to analyze the efficiency of an algorithm as its input approaches infinity, which means that as the size of the input to the algorithm grows, how drastically do the space or time requirements grow with it.

For example, let's say that we have a dentist and she takes 30 minutes to treat one patient.

As her line of patients increases, the time that it takes for her to treat all of the patients will scale linearly with the number of patients waiting in line.

This is because it always takes her a constant amount of time to treat each individual patient which is 30 minutes.

This gives us a general understanding of how long our dentist would take to treat 10 patients 20 patients or even 100,000 patients.

This is because since we know that the dentist takes a constant amount of time, which is 30 minutes to treat each patient, we can always calculate the time it would take for her to treat any number of patients by multiplying the number of patients times 30 minutes.

With this in mind, we can categorize her efficiency as being linear.

Or as we would say in Big O terms big O of n, where n is equal to the number of patients the time that it takes for her to finish her work scales linearly or proportionally with the number of patients, we use the same technique to determine the efficiency of algorithms, we can get a general idea of how functions time efficiency scales by categorizing a given functions efficiency the same way that we categorize the dentist's efficiency.

Let's create an easily comprehensible function that scales similarly to the dentist.

So this function is in the same linear category as our dentist, let's step through it and find out why.

To start the input to our function is an array with seven items inside of it.

For each of those items, we will log this expression which multiplies 1000 times 100,000.

Now don't let these large numbers for you, it will always take the same amount of time to multiply 1000 times 100,000.

Therefore this line of code takes constant time.

Which brings me to a very important point, when considering the efficiency of a function.

These lines that take constant time do not matter.

Well, at least for our purposes, they don't.

This is because if our array were some crazy length, like 200 million, changing this expression to something simpler, like one plus one would have a negligible effect on the efficiency of the function as a whole, we'd still need to iterate through 200 million items in an array.

In fact, even if the function looked like this, we would still ignore all of these constants and say that this function scales linearly or is big O of n.

Similarly, if we think back to our dentist example, we see that she took 30 minutes per patient.

But even if she took three hours per patient, the amount of time it takes her to see all of her patients will still scale linearly.

This can be difficult to grasp at first, but it starts to make sense over time.

So in the last slide, there was a lot of talk about ignoring the constants.

But what exactly is a constant? A constant is any step that doesn't scale with the input to the function.

For example, the time to evaluate this expression does not change with the input because both 101,000 are constants.

That is, these values are always the same, this expression always results in the same value.

And it always takes the same amount of time or constant time to return the same result.

Just like we use big O of n to describe linear functions.

We also have a big O name for constant algorithms, which is big O of one.

A good way to think about it is every line of code is actually a function in and of itself, which is actually true.

For example, let's reintroduce this function.

So this line of code is the reason why the entire linear func function is O of n because as you can see as the size of n increases the number of iterations that the for loop must traverse increases as well.

But let's take this second line into consideration.

Let's for one second pretend that we have a function that contains only this line.

Now as you can see, with this function, we pass in an array, but the function does nothing with the array.

The only operation within the function is constant because it doesn't scale with any input.

So regardless of how large of an array is passed to this function, This line always produces the same result.

And this is the only line in the function.

So therefore, this entire function is over one.

But wait.

In this function, we have multiple lines that are over one yet we still prioritize the line that is O of n and ignore the O of one operations.

Why is this? Well, this brings us to our last important note, in bego, we have a growth hierarchy, which looks something like this.

Now, don't panic, you don't need to understand all of these just yet.

So let's only pay attention to the ones relevant to this video, or even an old one.

We'll learn about the other ones in following videos for this series.

This chart shows the efficiency categories in order from good to bad.

That is to say that this first case of one is the best case.

And this last one is the worst case.

In big O notation, when determining the efficiency of an algorithm, we only care about the worst case.

So that means that the worst case where the highest order operation trumps the operations that have better performance.

So if we add the performance of all of these lines up, like so all of the lines of code that are o of one get cancelled out because oh Vin is the worst performing or highest order part of the function.

And this, ladies and gentlemen, is why we ignore constants, because we're actually just eliminating the non dominant items.

Because as a functions, input moves towards infinity, constants become less and less significant.

So to recap, when evaluating an algorithms efficiency, we must take into consideration the efficiency of each step within the algorithm, we then find the highest order step, or the step that has the worst performance, and prioritize it over all of the better performing steps, steps that are constant, or that are over one or as good as it gets in terms of efficiency.

So we always ignore them, unless the entirety of the function is constant, or o of one.

And in that case, we would categorize the entire function as constant or o of one.

And that Ladies and gentlemen, is your answer to what is big O notation.

Okay, so to understand O of n square, we're going to need to take the function into consideration in the function will look something like this.

So what this function is doing is it's going to take in a number in and it's going to iterate through this for loop starting with the number zero all the way up until the number in and for every iteration of this top for loop, we're also going to loop through this nested for loop.

And this nested for loop is doing the exact same thing that this for loop is doing.

It's iterating through every number, starting with zero up until the number in and within this nested for loop, we're console logging the coordinates for a sell within a matrix.

But to make things clear, instead of illustrating a console log of the index i and j, I'm just going to draw a square where these coordinates should be for every iteration of this nested for loop.

So if it sounds confusing, just try to bear with me, I promise it'll become clear.

Okay, so let's say for example, that we call the square function with the number four.

So that means that we're going to iterate through this top for loop starting with starting from zero, and then we're going to iterate all the way up until I is no longer less than four, once I becomes equal to four, then we will stop the iteration.

And then that's only for this top for the for each iteration of this actual for loop, then we're going to loop through the entirety of this nested for loop and do this console log.

And instead of logging the coordinates, like I said, we'll draw a square where the coordinates would be, so you guys can visualize this better.

So let's go ahead and get started.

So for the first iteration, is going to equal zero, and then we move on into this nested for loop.

And then we're going to iterate through the entirety of this nested for loop.

So right now i and j are zero, so i and j are both zero.

So we're currently at the first iteration of this for loop in the first iteration of this for loop, and we'll draw a square and then we move up one iteration of this for loop, so j becomes one and we'll draw another square.

And then j becomes two, it will draw another square and then j becomes three, and we'll draw another square and now j is four.

And since j is four, that means that j is no longer less than n, because n is four, and j is four, and n is four.

So j, and n are now equal, so will no longer iterate through this for loop.

So now we go back up to this for loop.

And now I is equal to one, so i is equal to one, and j is equal to zero, so we'll draw a square and then i is equal to one is in j is equal to one so we'll draw a square and then i is equal to one and j is equal to two.

So draw a square and is equal to one and j is equal to three, it will draw a square.

And now back to this top for loop again, because j and n are now equal, we're back up to this top for loop again, now i is equal to two, so i is equal to two, and j is equal to zero, so we'll draw a square and then i is equal to two, and j is equal to one, so we'll draw a square and i is equal to two, and j is equal to two.

So we'll draw a square and i is equal to two, and j is equal to three, so we'll draw a square and then now j is equal to four, which is our in, so will no longer iterate through this nested for loop, and we move back up to the top of this for loop, now, i is equal to three, i is equal to three at this point, and j is equal to zero again, so we'll draw square is equal to three and j is equal to one.

So we'll draw a square j is equal to two, j is equal to three.

And then j is equal to four.

So we no longer iterate through this nested for loop.

And at this point, our i is now equal to four and our n is also equal to four.

And we only iterate through this top for loop as long as r is less than in but our eyes now equal to our in.

So now we stop iterating through this top four loop.

And what we're left with is this matrix here.

And the reason why I said that these are coordinates for cells within a matrix is because this here is a matrix.

And these are rows.

And these are columns.

So we can look at AI, as being our column.

And then we can look at j is being row.

So for each iteration 0123 of our column, we also have an iteration for row 0123.

So coordinates being zero, and zero, were the coordinates for this square, and then zero and one are the coordinates for this square, and zero, and two are the coordinates for this square, and so on, and so forth.

So what does all this have to do with oben square? Well, hey, just one quick interruption.

If you are finding this video helpful, or it's bringing you to some type of understanding, please take the time to like and subscribe.

If we think about it, this is a square matrix, that is each side will be of the same length.

And by length, I mean 1234.

This is of length four, and 1234.

And this is of length four, and to find the area of a square, we just need to multiply the length of one side by itself, because every side of a square is of the same length.

So if this were a rectangle, we would multiply the width times the height, but for square, we can just multiply by itself because the width and the height will be the same length.

So to get the area of this square, we're just going to multiply four times four, four times four.

And that's going to equal the number of cells within this matrix, which also happens to be the number of times that we had to perform this code, which is four times four is 16.

And four times four is the same thing as four square.

So O of n square, our n is actually four.

And that is why typically functions with nested for loops, like a for loop and a for loop nested within it like this function is considered over in square.

I hope that makes sense.

Okay, so to understand all of in queue, let's take a function into consideration.

This cube function takes in an argument in which is a number.

And it's going to iterate through this for loop and for every iteration of this for loop is going to iterate through the entirety of this for loop.

And for every iteration of this for loop, we will need to iterate through the entirety of this for loop.

And I'm going to have to apologize ahead of time for my disappointing drawing skills.

But to illustrate this, I'm actually going to have to draw three dimensional shapes, which is not something that I'm entirely good at But anyways, for now, let's just ignore this image.

For now.

Let's focus on this function.

So for the top level for We're going to be iterating up until in.

So if we pass the number four to our cube function, we'll end up here at this first for loop.

And we're going to iterate starting from zero all the way up until n, which is four.

So let's get started.

So for our first iteration of this top level for loop, I is going to be zero.

Now for all the in cube, we're adding in additional nested for loop.

So there's no longer just a row and a column.

Now we have rows, columns.

And we also have this third dimension here, which we'll just call height.

So we have the columns that go in this direction, the rows that go in this direction, and the height that go in this direction.

So at this point, we're working with a three dimensional array, it's no longer a two dimensional array.

And it's the same concept.

So it's not as difficult as it seems, we're going to draw it out now.

So we would start with this initial for loop, and is going to start off as zero, right.

And we'll say that this initial for loop is representative of our columns.

So we can actually go ahead and write these numbers out just so you guys can see.

So we'll say that when I zero, this column is zero.

When I is one, we're talking about this column.

When I say two, we're talking about this column, and one is three, we're talking about this column.

And of course, once I becomes four, we're no longer going to iterate through this for loop because I is then no longer less than n, which is four, it will be equal to four.

And we can say the same thing for the rows.

So we would say that row zero would be here, row one would be here, row two would be here, and row three would be here.

Now I apologize if this is difficult for you to see, it's three dimensional.

So it's not really easy to draw this, but I hope that you guys can visualize what I'm trying to say.

And then the same thing for the height, the height would be represented by this for loop here.

So okay, and let's actually, I'm sorry, I should, I should actually just name these by the letter that we're using in the actual function.

So instead of calling this height, we'll call this K.

Because it's representative, this this for loop is represented as representing k here, so we'll just call this k as well.

And instead of calling this columns, we'll call it AI.

And instead of calling this rose, we'll call it J.

So for every iteration of this for loop, we're going to be moving up this k axis.

So if we were to write in what the index is for K, it's going to kind of be hard to see right now.

But it will be 012.

And three, so let's try to draw this out.

So let's do this step by step for a little bit to get you guys understanding what's happening.

So for this first iteration of this top level for loop, is going to be equal to zero.

So that means that I, this line, we're going to be here at the zero index of I.

And then for this nested for loop, J is also going to be equal to zero.

So j is here.

And we're going to be at zero here.

So we're still going to be here.

And for K as well, this for loop here.

This x is here, we're also going to be at zero, which is here.

So we're still going to be here.

So instead of console logging these coordinates, we'll just draw a square for this coordinate.

So this coordinate is 00, and zero, and 00, and zero, so we'll just draw a square here.

And again, you're going to have to excuse my poor square drawing prowess.

And since we continue with K until K is no longer less than n, we're going to continue to iterate through this for loop.

So to help you guys out, I can just tell, I can just write I right now is equal to zero, J right now is equal to zero and K.

It was equal to zero, but we just do the square for K at zero.

So now K is going to iterate it's going to increment one.

So K is now going to be equal to one.

So when k is at one, and j is at zero, and is at zero, so i j.

k is at one, then we're going to go up another square and this is going to be kind of hard to see because I'm literally trying to draw three dimensional space Whereas here and I'm just like terrible at drawing, I'll do my best.

Give that one more go.

Okay, so once we do that k increments one, so K is now two, two is here, and then i and j are still zero, so we're still going to be at j here.

So we're still going to be in this section.

So we'll draw another two dimensional square here.

I mean, two dimensional cube, excuse me, if I call a cube square, that's definitely not right cube.

So there's another cube.

And of course, K is going to increment again.

So then K is going to become three.

And then at three here, we'll drill another square, I mean, cube, sorry.

And at this point, K is going to increment.

And then it's going to be equal to four.

And once k is equal to 4k is no longer less than n, because n is also four.

So now k is equal to n.

So this world is done.

And now we move up to this for loop.

And this for loop will increment one and j will then be equal to one, because for each iteration of this for loop, we go through the entirety of this for loop.

So we've gone through the entirety of this for loop.

So now we can move up one iteration in this for loop.

And we can't move back up to this for loop until we iterate through everything within this for loop.

So we're still on so we're only incrementing the row and then we're going back into iterating K.

So now that j is equal to one is still zero, so we're still here, we're still here, because this is the column and then I still zero, this is I and I still had zero.

And we're still here, but j went from zero to one.

So now we're here.

So we're back into k, and k is going to start off zero again.

So at I being zero, J being one and K being zero, because zero, okay, this is K, and this is zero.

And we're here we'll draw a square.

Sorry, once again, I said square Yeah, we'll draw q 10k increments.

We'll draw another cube.

And then k increments, and we draw another cube.

And then k increments.

Individual one more Q, because once k reaches four, so yeah, K, okay, we'll increment one more time, and it'll reach four.

And now K is no longer less than in.

So we go back up to RJ for loop, and that will increment one.

So this one will now become two.

And it's pretty much the same thing.

Throughout the entire throughout the entire function, and it's getting hard to see the cubes that I'm drawing here.

But eventually, we'll get to a point where the entire cube is filled in, which will look something like this.

So we'll get to a point where the entirety of this cube would be filled with these miniature cubes, which are just the iterations of these four loops.

So once we get to that point, and thank you cube is completely filled in.

At that point, that means that we have iterated through the entirety of this top level for loop.

And feel free to take the time to try and draw this out on your own.

But I basically went through as much as I could with the time that I have in this video, but it's pretty much the same thing until the entirety of the cube is filled.

So once all these four loops have completed, you'll be left with the cube that looks like this.

And since this is a cube, that means that its height, and its length, and its width, are all going to be of the same length.

And that is to say that they're all going to be in because if you look here we went through in iterations of J.

We went through iterations of AI And we went through in iterations of K.

And again, I'm sorry, for my poor drawing, I hope that you get the idea.

So if n is four, this is going to be four, this is going to be four, and this is going to be four.

And to get the volume of this cube, to get the volume, the space within this cube, since we know that all of these are going to be the same, we only need to know one of them.

And one of them to get the volume we just do for this case for cube, and four cubed is 64.

And that will be the volume of this cube, which just means that there are 64 of those of these miniature cubes within this larger cube.

And that's the volume.

So O of n cubed, r n is four.

So o of four cube, which equals 64, which is the volume of this cube.

which also happens to be the number of times we would perform this function console log the coordinates, but in our case, we just do the squares.

And that is why this function is O of n cube must first understand what a logarithm is.

Simply put a logarithm is the power that a number needs to be raised to to get some other number.

I know that doesn't make much sense out of context, but don't worry, I've got you covered.

Let's take the number eight into consideration.

So we want to raise some number to some power to get a PhD.

In computer science unless specified otherwise, we can always assume that the number that we want to raise to sum power is two.

So let's rewrite this.

So we want to raise two to some power to get eight.

So this same equation can be written like this, or this two here is called the base.

And let's not forget that in computer science, the base is always two.

So to find the answer to this, we just need to find the answer to this.

With that in mind, we can see that if we raise two to the power of three, we get the number that we're looking for eight, so log base two of eight is three.

So with all of that in mind, let's move on to the meaning of Oh login.

For this portion, we will be using a very bare bones recursive function to visualize Oh login, but don't worry, I will walk you through every step.

Just stay with me.

So we will start with a number and we will use eight so that you can easily see how this relates to our explanation of logarithms in the previous slide.

So this variable in we will be passing to our recursive function that looks like this.

So this functions time complexity is Oh, log in, let's dig deeper to find out why.

For now, let's just ignore this first line and focus on what the function is actually doing.

So when we pass a number into this function, it divides in by two or splits it in half, and then calls itself with the new half or divided number.

Let's visualize this using the graph.

So we first call the function with the value eight, this eight is then divided by two.

The function then takes the result of the division and passes it recursively to itself as the new value for n which in turn results in us going one level deeper.

We then do the same thing with our new value for n which is four, that four is divided by two resulting in a new n.

And the function then passes our new value for n to a recursive call to itself again, resulting in us going one more level deeper.

We then do the same thing with our most recent value for n which is two, we divide it by two and the function once again recursively calls itself at this level we will stop is we can no longer divide in without getting fractions as the result.

Now we have arrived at the beginning of the secret to understanding Oh login, so watch closely.

If you look at our graph, you will see that we've gone one to three levels deep.

If you recall from our previous slide, the log base two of eight is three.

Our input in is eight and we've gone three levels deep.

You will also notice that we have to raise two to the power of three or multiply Two times two times two to get eight.

And since division is just the inverse of multiplication, we can see that when we do something like this.

So that means that this function has a time complexity of Oh, login.

Why? Because our n is eight.

And in computer science, our base is always two.

And we must have our n three times or go three levels deep in our recursive function to get to a point where we can no longer reasonably have our input in, which is another way of saying that log base two of eight equals three.

And that, ladies and gentlemen, is the secret to understanding Oh, login time complexity.

And as a quick note, this is not only applicable to recursive functions.

And if you're curious about that line of code that we covered up earlier, all it does is make sure we stopped dividing in when n becomes one or otherwise, the function would keep dividing fraction after fraction until we eventually exceed the maximum call stack.

So we'll start with a very simple function, which contains only a while loop that assigns a new value to the variable in for each iteration.

And for this example, let's imagine that we're passing the value eight two hour in for this function.

So that means we'll iterate through this while loop as long as eight is greater than one.

And for each iteration of this while loop, we're going to divide our n by two and reassign it to n.

So our n is going to be halved for each iteration.

So currently, our n is equal to eight, because we passed in eight as in and while n is greater than one, we're going to iterate.

So right now is eight, which is greater than one.

So we'll do this math dot floor n divided by two for our first iteration, which would set our n equal to eight divided by two, which is four.

And this math dot floor, all it does is it floors the result of our division.

So for example, if we have math dot floor, five divided by two, we would get two here, instead of 2.5.

So after this first iteration, our in is now equal to four.

So while n is greater than one, we're going to do another iteration.

So four is greater than one, so we're going to do this again.

And n is going to equal four divided by two, which is going to equal two.

So now our n is equal to two.

And while n is greater than one, we're going to do this again.

So in is currently greater than one, two is greater than one.

So we're going to do it again for third iteration.

So in is going to equal two divided by two, which is going to equal one.

So at this point, our n is equal to one.

And we're going to go to this condition here again.

So while in is greater than one, we're going to do this.

But right now n is equal to one, it's no longer greater than one.

So we're not going to continue with this while loop.

So why is this function of login, so our n is eight.

So that means that this function should be o of log eight.

And if you remember from the previous video on old login complexity, this is just the same thing as o of log base two, eight, which just means what power do we need to raise to buy to get eight.

And if we write this out, what power do we need to raise to buy to get eight, we see that we need to raise two to the third power to get eight, because two times two times two equals eight.

So this three is what's important, because division is just the inverse of multiplication.

So if we need to multiply two times two times two to get eight, then we should also be able to divide eight by two three times to get one.

So there's 123.

So that means that for this function, when we pass in a value for n, we're always going to need to divide this value in By to log in times before we can get one, which is just another way of saying that when we pass into this function, we're going to iterate through this while loop, log in iterations, before we get to the value one.

So if you see here we have one iteration, two iterations, three iterations.

So there's three iterations here.

So this is this three is log in iterations.

Because again, oh, all log in, just means Oh, log base two of eight.

Because our n is a, n, log base two of eight is three, because two to the power of three equals eight, which is our n.

And that is why this non recursive function is oh log in, because there will be log in iterations 123.

Before this while loop ends.

I hope that makes sense.

To start, we should understand that in order for binary search to work, the array that you were searching must be an ordered array, both ascending and descending order two arrays will work.

Let's start by visualizing our array.

In practice, this is much more useful as the size of an array becomes much larger, but we will stick with an array containing nine elements to help us understand the concept more clearly.

So let's assume that we want to check our array to see if the value 100 exists inside of the array.

The naive solution would be to iterate through each element of the array checking to see if the value is equal to 100, like so.

But for this method, we have to iterate through every element in the array up until the value that we're looking for.

What if we have to do this for an array containing 1000, or 100,000, or even a million elements.

This is where something like binary search can be useful.

So let's try this again.

So here, we're still wanting to check to see if the value 100 is in our array.

But this time, we'll use binary search to figure this out.

To start, we need to find the midpoint of our array, which is just the element in the middle of our array, our midpoint is here.

Now since our arrays in ascending order, we know that anything to the rate of our midpoint will be a value that is larger than our midpoint.

And everything to the left of our midpoint will be a value that is less than our midpoint.

So we need to figure out if this number 100, which we are searching for is greater than or less than our midpoint.

This will tell us which side of our array our numbers on.

So if we simply write out 43 is less than 100, we can actually see that the side of the array that our numbers on is this side.

To paint a full picture, let's for one second pretend that the number we are searching for is two and not 100.

In this case, two would be less than our midpoint 43.

Therefore, it will be on the left side.

And this Ladies and gentlemen, is why binary search will only work on ordered arrays.

Because without the order, there would be no way to tell which side the number we're searching for is on by comparing it to the midpoint.

Now let's get back to the original number that we were using for our example.

So now that we know that 100 will be on the right side of our midpoint, we can completely do away with anything to the left of the midpoint including the midpoint.

So what we're left with is this, what we've done is we've essentially cut the array in half.

To put this in perspective, let's imagine that we have an array with 1 million elements and we divide it by two.

In just one step, we will have cut down the number of elements that we would need to search by 500,000 elements as opposed to iterating through all 1 million elements and searching that way.

And it doesn't stop here.

We will now do the exact same thing with this half of the array.

Let's remember that we are searching to see if the number 100 exists within our array, we will first need to find our midpoint.

Now don't be confused by the even number of elements in this array.

Although there won't be an even number of elements on each side of our midpoint, it does not actually matter because we actually just need to split the array approximately in half.

For example, to find the mid and code we will do something like divide the length of the array which is four by two.

That resulting to we would use as the index of our mid.

So let's write out the indexes of this array remembering that arrays are zero Meaning that the starting index will be zero.

And if we take this resulting two and see what value it points to, we see that our mid is 100, which is the number that we are searching for.

So in that case, we would be done, we have found our number.

But to prove that which one of these we choose to use doesn't actually matter, let's explore what would happen if the mid 54 were used is the number that we're looking for greater than or less than our mid 54.

Our number is greater than 54.

So that means that we can get rid of the left side.

And what we're left with is an array containing only two elements, which again, is an even array.

So we have no way of determining which one we should choose as our mid let's see, what would happen if we use 124 is our maid is 124 greater than or less than 100.

It is greater than, so we can ignore the right half of this array.

Now we're left with an array containing only one element.

So our so called midpoint can only be this element.

And this element is the number we're searching for.

So we're done here.

So as you can see, regardless of if you have an auto array or an even array, as long as it is ordered, the search for element will be found if it exists in the array.

And that Ladies and gentlemen, is how binary search actually works and why it is useful.

So let's just start by creating a file and we can call it log in dot j s.

For binary search to work, the array that we're searching must be in either ascending or descending order.

So you can't just have a randomly ordered array and use binary search on it.

So that's just something to keep in mind throughout the rest of this tutorial, our binary search function is going to take in four arguments, it's going to take in an array, and the array is just going to contain integer values, which will need to be ordered, so we will just do one through eight, we'll also need to pass in the first index of our array to the function, we'll just call it start.

And that's just going to be zero.

And we will need to take in the last index of our array, which we'll just call end.

And we can get that by getting the length of the array and subtracting one from it.

The reason we need to subtract one from the length of the array is because the index is of the array are actually zero based, but the array itself, the length is actually not zero based, it's just going to be the number of elements in the array.

So the array length is going to be eight, but the last index of the array of length eight will be seven.

So that's why we subtract the one.

And then last but not least, we'll need to take in a target value, which is the value that we're searching for.

And we're going to just search for eight.

And then we can start building our function.

And we'll just call it binary search.

And it'll take in the array start at the end and the target.

And this function is actually going to be a recursive function.

So to start this function off, we need to find the middle index of our array.

So you'll notice that we're using a built in function math dot floor here.

And the reason we're using this is because if we go to the definition, it says that it returns the greatest integer less than or equal to its numeric argument, which basically just means that if this the division expression within our parentheses, within our function, parentheses return something like 5.5, the value assigned to MIT would only be five, because we don't want to take into consideration anything after the decimal point because we just want to find an index, which of course there wouldn't be an index 5.5.

So therefore, our mid would just be five.

And the next thing we would want to do is check to see if our midpoint is actually the number that we're searching for, which is our target.

So this would basically return true if the mid value of our array is actually the target that we're looking for.

So we're returning true because that means that the value that we're searching for exists within the array, and we would be done here.

And actually, I just realized I might actually be confusing you guys by referring to our mid and our mid value interchangeably.

So this mid here is actually the index of our mid which we're trying to get we're trying to get the index.

so here we can just add index as well.

So when I say our mid, I'm actually referring to the valley So we actually want to return true if the value that's at our mid index is equal to our target value.

So if the value at our mid index is not equal to our target, we then want to go on to check to see if the value at our mid index is greater than or less than our actual target.

So actually, this should be made index.

Sorry about that.

And actually, we have another error here.

So we'll start and then target should be here.

That should work.

So yeah, let's take the time to understand what's happening in this line of code here.

So if the value at mid is greater than our target, then that's going to mean that our target is actually in the left side of the array.

Because if we look here, and we take into consideration that five is going to be our mid in this situation, in the first execution of this function, five is going to be our mid.

And if five is greater than the number that we're searching for, then that means number that we're searching for is going to be in the left side, because if five were, if the number that we're searching for were greater than five, then it would be in the right side of the array, because our array is in ascending order.

So this is to check to see if the item that we're searching for is in the left side of the array.

And if it is, what we're going to do is, we're going to pass in our start, which is going to remain the same.

So we're going to keep the same start, which is going to be in this case, it's going to be index zero, and then our end is going to be mid minus one minus one, because we're going to actually do away with our actual current mid and actually, well, this should be nid index as well.

We only need to assign the current mid minus one to our in variable, because our next execution of the function would have this as our end, and then this as our start, and therefore we'd only be searching 1234, which we would then in turn find the mid for 1234.

And then we would do the same thing.

So now what would happen if the target value that we're searching for is greater than our mid value? Well, let's see.

So in this particular case, the target value would be less than or mid.

So that would mean that the target value would be in on the left side of our right.

But if that were not the case, then if our target is larger than our midpoint, then we would do something like else return.

So we're still going to function still going to call itself of course, but this time, we're going to pass in the array, the array, and instead of passing in the original start point, we're going to be passing in the midpoint index plus one.

And that's going to be our new start point.

And this is because we're starting from the midpoint to the right side of the array, because the actual value that we're looking for is in the right side of the array, and then at this point, our end can just stay the same, because the end is just the end of the array.

So let's let's have a look at this again.

So so let's again, pretend that for this execution, our mid is five and but this time, the actual value that we're searching for is greater than our midpoint.

So that means that it can't be on this left side, because everything on the left of our midpoint is going to be less than because our arrays in ascending order.

So it's going to be on this right side.

And if it's greater than our midpoint, then of course, we don't need to take five into consideration, which is why instead of doing mid index, and in instead of returning mid index and end to the function, we only need to return mid index plus one, which is going to be this index here, it's going to be index, it's going to be this value six at the index one index above our actual mid.

Now at this point, we're only searching our end and our mid plus one.

And we're only searching these three elements in the array.

That's what both of these conditions cover.

So this first condition covers if the item is to the left of our method, which is over here.

And the second one covers if the item that we're searching for is in the right environment.

And this is how binary search works.

This is why binary search is more efficient than say linear search.

Because we don't need to check every element in the array we can actually essentially eliminate half of the array by knowing whether or not the item that we're searching for is less than or greater than The midpoint.

So let's go ahead and see if we can actually run this function and get it to work.

And I'm going to tell you right now, we're going to try and run it twice, we're going to try and run it searching for the actual value that we know that's in the array.

And we're going to try and run it searching for a value that's not in the array.

And you'll see that we're missing something in this function.

So let's go ahead and try and run it.

Now to run it.

Obviously, we have to invoke the function.

So we'll go binary search.

And we're going to pass in array, start and end target.

And we're going to save that.

So we will try and write it by just using node, login dot j s.

And we broke it.

Nice.

Got to add in the target here.

So it caused the entire function to fail.

See it again.

Okay, so let's see what happens if we actually return the value, I mean, console log the return value of the function.

And we get true because eight is found within the array.

But what you'll see here is if we search for something that doesn't exist within the array, we're going to break it again.

So 10 does not exist.

So let's try it again.

And we got maximum call stack size exceeded, because let me show you what it means maximum call stack size exceeded.

So what we're doing is, every time we don't meet this condition true, we're going to call binary search again, which is we're calling the functions recursively calling itself again.

And if we're, if we're searching for a number that doesn't exist within the array, binary search is basically going to keep calling itself recursively.

And there's never going to be a point at which it stops.

Even if it doesn't find the item within the array, it's still going to continue to recursively call itself until eventually we reach the maximum call stack size, which is basically you've exceeded the amount of memory allocated to this particular application.

So to solve this issue, what we want to do is we want to add a base condition that will stop the function from recursively, calling itself after it's checked the entirety of the array.

So we can do if start is greater than and then return false.

So the reason why this works is because if the targets not in our array, it either means that the target is larger than the largest value in our array, or it's smaller than the smallest value in our array.

So that means our function will keep checking our array until eventually we get to either the largest item if the target is larger than the largest value in the array, or it gets to the smallest item if the target is smaller than the smallest item in the array.

And at that point, the start and the end values will be equal and at the point where both the start and the end values are equal passing our start in our into either this line, or this line, well, in effect, make the start greater than the end.

And now we can run this again using this tin that doesn't exist within our array.

And as you can see, we get false.

And if we even added negative here, negative 10 doesn't exist.

So we get false as well.

And let's see, what else can we try.

just tried to we know two exists.

And then and we get through.

So let's change this back to a to get a feel for why this function is oh log in, let's actually let's go ahead and create a longer array here.

So currently, our array only contains these eight elements.

And it's going to be kind of hard to get a general understanding of the way that our input scales with such a small array, so we can go ahead and just just empty out our array, and we'll just create our own array.

So let's see, the trade our own array we can just do for i equal zero, i is less than 1024 i plus plus.

And then here for each iteration of AI, we can just do grade up, push high.

And let's think let's actually make eye one.

And then we'll make this less than or equal to.

And then after that we can console.

log our array.

And for now, let's just comment this out.

And let's see.

Okay, so at this point, we have a longer array, which will hopefully help for you guys to visualize how the input is scaling when I do some console log trickery here.

So yeah, so we don't need to log this anymore.

Just delete that, actually.

So we're creating a new array here.

And it's going to be an array that has elements from one to 1024.

And for the purposes of this example, I don't want us to find the element, I mean, the item in the array, so we're just going to change this to something that doesn't exist within the array.

So we'll just put it like that 100,000 does not exist within our array, and also the end, and this is getting the end from this current array.

So we're going to need to bring this down to after we create our full array.

So this array is empty here, and then we're adding all of the values in this for loop and then we get the end of the array.

And the start, of course, can still be zero because it's zero.

And also, we can go down here and delete till the, we don't need to console log this anymore, because we're going to do another console log.

So we're going to execute the function here.

And then here is where we're going to try and make some magic happen.

So for each call to binary search, like each recursive call, we want to not just recursive call the first call for the first call.

And each recursive call, we want to log with the array that we're searching through is looking like.

So in the beginning, it's the full array, which we just showed when we console logged in earlier.

And then at each call to the function, the rate is going to essentially be halved.

So it's going to look something like let's see, console dot log will do array dot slice.

And we're going to do the start and the end.

So what that does is, it's only going to show the parts of the race from the start to the end, it's not going to show the full array anymore.

And let's see if that works.

so here we can do node, log in.

Okay, and yeah, that worked.

So maybe I can make this smaller.

So you can see, so when I make it smaller like this, it's kind of easy for you to see like, well, at this point there is too long to show its entirety.

But you can still see what's happening here.

So like since the value is greater than the left side of the array, you can see that all these lower values are going to essentially be eliminated, and it continues to get halved and have an halved.

And here's where you can start to see visually what's happening here like I can see that it's the ray is continuing to get smaller and smaller.

To understand ovan login, we will take this small function into consideration.

This function has a complexity of ovan login.

Let's step through this code line by line so that we may understand what is happening here.

This function takes one argument in which for the sake of this example will be for we then declare another variable y which we will set equal to n, we will get to what this variable Y is for later.

And at this point, we have a while loop that iterates through n until n is equal to one.

For every iteration through in this code within the while loop is run.

Let's visualize this.

For the first iteration of the while loop in starts off is four but we divide it by two, so n is now equal to two.

Then we get to this line of code which is the start of a for loop.

This is where this variable y comes in.

The reason we declared this variable before the start of the loop is because n is getting divided by two for each iteration.

This in turn is reducing the size of the variable n.

But for this inner for loop we needed to iterate through the original size of our original n.

So we stored the original end in a separate variable.

Okay, back to this inner for loop.

For each iteration of this for loop up until the size of n we will log or print the value for I.

Once this is finished, we move on to the next iteration of the while loop and repeat the process going into this iteration In is now two, we start by dividing in by two.

So n is now one.

And once again, we iterate through our inner for loop up until the size of y.

Now at this point, you will notice that our n is now one.

If we check the condition of our while loop, we see that we only want to iterate while n is greater than one.

So the while loop will now terminate, and the function is finished.

Now, after all is said and done, and with everything written out, we can see that there's a top level loop here.

And there's an inner loop for each iteration of the top level loop.

So this is where the magic happens.

So pay close attention.

For every iteration through the top level loop, which iterates until n is one in is divided by two.

This means that this top level loop never actually iterates through the full size of our input in the value for n is being split in half for each iteration, which is why we would say that this top level loop has a complexity of Oh login.

If you are confused about why this top level loop is Oh, log in, let's take some time to prove it by writing it out.

So this is Oh, log in.

Let's plug in some numbers.

Now if you've watched my video on Oh, log in, you know that in computer science, the base of a logarithm is always two unless stated otherwise.

So this can be rewritten as log base two of four, four, because we're replacing in with our actual input for n, which is four.

And log base two of four is two, because you need to raise two to the power of two to get four.

And as you can see, this makes sense, because for this top level loop, we only iterate two times.

So for this top level loop, we have log base two of four equals two.

Now we need to take a look at what is happening in each of the two iterations of the top level loop.

For each iteration, we loop through the full size of y, which is the original size of n.

So that means that each of these inner loops has a complexity of O of n, which just means that processing time increases linearly with the size of n.

Now this is where we bring everything together.

O of n log in really just means O of n times log in.

And if we plug in some numbers here, we get this.

Because remember, log base two of four equals two.

And if you look at our visualization, it makes perfect sense, because for each iteration of the top loop, we iterate through the entirety of y, which is our original value for n.

And that, ladies and gentlemen, is how you visualize all of in log in.

So we can start by creating a file, let's just call it merge sort, well then create a function, which will also call merge sort.

The argument to this function is going to be the array that we're looking to sort for the first portion of this function, we'll need to make sure that the array that we're passing in has a length greater than one, we will need to do this because if the array is only if length one and there's only one element in the array, then it is already sorted.

This will also be our base case, as this merge sort function is going to be a recursive function.

Next, we're going to need to split our array in half.

To do this, we'll first need to find the middle index of our array.

So with this math dot floor here does is it makes sure that we only take into consideration the base number from the result of the division.

So for example, if we divide a number that results in I don't know, let's say 5.5, we wouldn't take into consideration the number after the decimal point.

So we would only return to the variable the number five.

And this is because when taking indexes into consideration, there is no index 5.5 or 2.2 or 1.1, there would only be an index one, five or two.

So this is why we're using math dot floor here.

And once we have the middle index of our inputted array, we can then split the array in half and create a separate array for the left side and a separate array for the right side.

So we can do that by just creating a new array left array, and then we can set left array equal to the input array dot slice, and then the indexes are going to be the arguments that we passed.

So basically slices from and to.

So we want to slice from the first index of our input array.

And we want to slice up until the middle index that we just that we just got.

And that's because we want the left side of the array.

So let's say for example, the array looked like this.

And we win, we went ahead and got our middle index, which would be something like this three here.

And then we want to create an array starting from this zero index, up until our middle index, which would be the left half of the array, and then we would go ahead and do the same thing for the right half of the array.

So we're going to actually go ahead and do the same thing for the right half of the array, we'll just call it right array.

And we'll do array dot slice again.

But this time, we're just going to do from the middle index all the way until the index, the last index of the array, and the way we get the last index of the array is just by using array dot length.

And this here can actually be a bit confusing, because we know that array dot length gives us the length of the array, which is the number of elements in the array.

And we also know that array index is zero based.

So basically, if the length of an array is five, there will only be index 0123, and four, there won't be an index five.

So here, you might be wondering how this is actually working.

And it's because actually, there's an error.

And this method method is not slicers, just slice, but it's because this slice method slices up to in but not including in.

So basically this end value, it's not included in the actual array, slice, only the value before will be included.

So for example, if we have an array that looks like that looks like this, the end that we would use for this array would be three, even though that there's only index 01.

And two, it will slice up until end not including in so this is why we don't need to subtract a one from this because if we were to subtract one from array dot length, and use that as the last index, or the end index that is passed to the slice method, then we actually wouldn't get the full array, we would only get up until this one, but not including this one.

So they were able to only look like this in this slice.

I hope that makes sense.

It's a bit confusing.

And also keep in mind that with this example I just gave above, I'm actually not taking the middle index into consideration.

So for this array, in particular, it would look something like array dot slice, well, slice and there will be zero index up until array dot length minus one.

Anyways, last but not least, for our actual emerge cert function, what we're going to need to do is implement the recursive portion of the function, which is we're going to return and bear with me, we're going to return a helper function that we haven't created yet.

And we're going to call it merge.

And within this marriage helper function, we're going to accept two parameters, which is going to be the left array and the right array.

And what we're going to pass to merge is going to be the recursive call to merge sort.

And then our left array, and we're also going to pass in the recursive call to merge sort, and our right array.

This is going to seem a bit confusing right now.

But just bear with me, I will explain how this is working.

And I will try to make things clear for you.

But for now, we don't actually have this merge function, so we need to go ahead and create it.

So let's go down here and create this new helper function called marriage, which will take in the left array, and the right array.

Oh, sorry, and it's not merger, it's merge.

Now this function is going to be the function that actually merges the two arrays.

So the way that Merge Sort works is we use a divide and conquer approach in which the input array is basically halved until we have in arrays of length one, and at that point, arrays of length one, as mentioned above, when we created this space case, here, an array of length one is already sorted.

So to visualize this, if we have an array, that is one, there's only one element in this array, so obviously, this one is going to be the first and last element in the array.

So there's no need to sort it because there's nothing to compare it to with.

What we do in this actual merge function is we're going to bring these sorted arrays together and compare them and then sort those individual one element arrays.

So one thing to keep in mind throughout the process of writing this merge function is that this merge function is always going to take in two already ordered arrays, starting with the ordered arrays of length one.

So to start, we're going to To create a variable, which is going to just be the result array, and it's going to start off as an empty array.

So these all equals just an empty array.

And we're also going to define our base indexes for the left array and the right array, but could index equal zero.

Now we'll do the same thing for right.

Next, we'll create a while loop that's going to compare the two arrays element by element.

And actually stick here, this length.

So within this while loop, we're going to compare each element of both arrays and whichever element is less than the other will get added to the result array will then increment the index of whichever element got added to the result array because that element no longer needs to be compared.

If you're a bit confused by this, just bear with me, I'll actually create an illustration for you to understand it better.

But for now, let's just write out the code.

Let's imagine that the rays that we want merged look like this for the left array and this for the right array.

Now keep in mind that the merge helper function merges ordered arrays, so it will not work on unordered arrays.

In this example, we are merging two ordered arrays of length three to show the entirety of the functions functionality, but this will also work for naturally sorted arrays of length one.

So for this while loop to continue, both left index and right index need to be less than the length of their corresponding arrays.

As you can see, these indexes are incremented, every time that index is element is pushed to the result array.

So if we draw this out, it looks something like this.

Here are the two arrays and their indexes.

In this next line, we check to see if the element at the left array index, which is currently zero is less than the element at the right right index, which is also zero.

So it's three less than one.

No.

So that means we do what's in our else condition, which is push the right array element at its current index to the result array and increment the right array index.

And now our right array index is one so we can move this.

And then once again, we do our comparison at the top of the for loop is three less than six? Yes.

So we push three onto our result array and increment our left array index.

And we can move this over as well.

And back to the top of our for loop again, is 12 less than six? No.

So we're going to use the code in our else condition, which is push the right array element six to the result array and increment the right index.

And again, we will move this and now is 12 less than 15.

Yes, so we push the 12 from the left array to the result array and then increment the left index as well as move this arrow to the new left index.

Now is 16 less than 15? No.

So we move on to our else condition and push the 15 from the right array to our result array and increment the right index by one.

Now at this point, this while loop will terminate because if you remember this while loop will only continue if the left index is less than the left arrays length, and the right index is less than the right arrays length.

At this point, our right index is equal to the right arrays length.

As you've probably already noticed, there's still a 16 left in the left array that has not yet been pushed to the result array.

But the while loop is already complete.

So what do we do? After the while loop, we're going to add another line of code that looks like this.

So this return is going to return a single array that is a combination or concatenation of three arrays the result array, a slice of the left array and a slice of the right array.

So this slice function if we only pass one index to it, it will be used as the start of the slice and will slice up until the end of the array.

Let's break this down.

So if you remember from the last slide, our result array currently looks like this.

And we're going to add to it a slice from the left array starting from the left index that we incremented which is two which results in array containing only this part And we're going to add to that a slice of the right array starting from the right index that we incremented, which is three, which results in an empty array, because index three would be here.

And with all of those combined, the result being returned is an ordered array that looks like this.

Now let's go ahead and add in the return that we just discussed in the illustration.

And this completes our merge function.

And now that the merge function is complete, our merge sort function is also complete.

And now we can go ahead and test this out.

To test this, we will need to create an array.

And this array, we will need to pass to our merge sort function.

And there you have it, our sorted array.

And if we take the time to go back in here and have a look at the code, you'll see that within this merge sort function, we're dividing the input array into recursively, which makes this Merge Sort portion of the function of log in.

And actually, this merge function is all event because it needs to touch every element within both arrays to actually sort them.

So with this merge function being old in and the actual recursive merge sort function being of login.

For every level up until the depth of this recursive function, we're actually going to be doing this merge, which is O of n.

So to get the overall time complexity, we would just have to multiply the depth of this recursive function by O of n, which is O of n log in because of N log N is just multiplying in by log in and log in, in this case will be the depth at which this recursive function needs to traverse.

So let's visualize this merge sort function, we'll go through the code line by line.

So let's imagine that we have an array that looks like this.

So this array here will be our input array.

So this is the array that we're going to pass to our merge sort function here.

So this array is this array.

So the first portion of the code here, it just checks to see if our array is greater than length one, because an array of length one is already sorted.

So if we get an array of length one here, we're just going to return that array as an already sorted array.

But if the array is greater than length one, then we're going to move on to this portion of the code.

And this portion of the code is where the divide and conquer approach is implemented.

So basically, here, we're going to split our input array.

By getting the middle index of the array, we're going to split it into two separate arrays, which will look something like this.

And these individual arrays left array and right array.

After their split, they're going to be once again passed to the merge sort function.

Once again, we end up at this portion of the code, because this array and this array are individually being passed to this merge sort function.

So for each of these, we end up at this portion of the code.

And both of these arrays are not less than length do, we have an array of length two, and we have an array of length three.

So they're going to move on to this portion of the code in which we use the divide and conquer approach once again.

And let's go ahead and write that in here actually, because it's important.

So once again, we're going to get the middle index of our array and create a left right and a right array by splitting the single array on its middle index.

So you will notice that this array, this array and this array are already of length one.

And as, as we've seen here, we're going to pass these arrays of length one to merge sort, we're going to pass these arrays in to merge sort, and then they're going to get to this conditional, and they're less than length two.

So we're just going to return these rays.

So for these arrays, we can stop.

But this right here is of length two.

So this array is going to get to this portion of the code again, and we're going to split it.

And now, these arrays are of length one, so we can stop here as well.

So these calls to merge sort, are the same as these calls to merge sort.

But we still haven't called merge.

And what merge is going to do is it's going to take two already sorted arrays, and it's going to merge them together into one single sorted array.

And what that's going to look like is, it's going to be called here, these results are going to be merged together into one sorted array.

So these two sorted arrays are going to be combined and returned here as a sorted array of length two.

And the same thing will be done here.

We're going to merge.

And these two sorted arrays are going to be combined and returned here as a single sorted array.

And we'll do the same here.

Merge.

And these two sorted arrays are going to be combined and returned here as a single sorted array.

And last but not least, we're going to merge here.

And these two sorted arrays are going to be combined and returned here as a single sorted array.

And let's not forget our initial call to merge sort.

So that's how we can visualize recursive merge sort.

But you're probably still wondering what this merge function is actually doing.

So as mentioned before, this merge function takes two already sorted arrays, and it combines them together into one sorted array.

And that function looks something like this.

So as you can see, merge takes in a left array and right array, both of which are sorted, and then it will return this result array, which is a combination of both the left array and the right array sorted.

So to understand the time complexity of merge store, we'll take a array and array of length four into consideration.

So this input array will pass to the merge sort function.

And what that call to merge sort will do is divide the array approximately in half and those halves will be passed to merge sort recursively at this point, We have our arrays of length one.

So we can't split these rays any further.

And to understand the time complexity of merge sort, we need to understand, oh, log in.

So as we know, in computer science, so log in is the same as log, base two in, and in this case, in is the length of our array here, which is four.

So in the reason you need to understand login, is because this divide and conquer approach that we're implementing here is login.

That is to say that log base two, a four, which is our in our n is four equals two.

And that's because two to the power of two equals four, which means that for an array of length four, there will be two levels to our recursive tree structure.

And we can see that here, you have level one, and we have level two.

So this is a level, and this is a level.

And for each one of these levels, what we need to do is we need to touch every element of n, because we need to sort them.

And in order to sort them, if you remember from our illustration of merge, within this merge function, the while loop within this merge function, needs to touch each element to compare the elements and create the merged array.

So that means that for each level, we need to merge.

And this merge function needs to touch every element of n.

So that means that each level is actually Oh, then.

And there are log n levels.

So O of n times log in really just means Oh, of four, because four is our in, in is for 1234.

So four is our n times log, base two, a four.

And as we seen here, log base two, a four is actually just two times four.

So the number of elements in the array, and the number of levels that we need to traverse, so for every level, we need to touch in elements in the array, which is two times four.

And that's why mergesort has a complexity of O of n log in.

So we'll start by examining this recursive implementation of Fibonacci.

So let's imagine that we pass the number four to our fib function.

So at this point four is our value for n.

So after we call this function, we'll end up at our first if block.

And this if block just returns zero if n equals zero, and then we move on to a second if block in the second if block just returns one if n equals one.

So once we pass the number four into our function, we'll end up at this first if block.

And both of these if blocks are base cases, because as we know, with recursive functions, we need to have a base case so that the function doesn't continue to call itself even after we're finished.

So we pass the four into our fib function, and four is not equal to zero, so we don't return zero, and four is not equal to one, so we don't return one.

So we end up here.

And what this return does is it adds together the result of two more calls to the Fibonacci function, this first Fibonacci function, we're going to call with our n minus one, so four minus one, and the second one, we're going to call with our n minus two, so four minus two.

So let's have a look at what that looks like.

And as we can see, four minus one is just equal to three, so this would actually just be three.

And same for here.

This would just be equal to two.

So at this point, we have to call to our favorite our Fibonacci function.

One which we're passing three is our in and one numerator passing two is our in.

So for both of these calls, neither one of these will Return at these IP blocks.

So we'll end up back down here again, which will look like this.

And again, we can just do the math in the parentheses.

And let me just make this a little bit smaller.

So at this point for these three calls to the Fibonacci function, we're going to reach our base case, because we're passing zero for this call.

And we're going to just return zero at that point.

And we're passing one for these two calls.

And we're going to just return one at those points.

So these are going to be complete.

These ones are done.

And for this function we're passing to is our n, which isn't equal to zero and is equal to one.

So at this point, we'll then again go down to this portion of the code.

And now these two have reached our base cases as well.

And one more time, I'll need to shrink this.

So now we'll get into the reason why this recursive Fibonacci function is an exponential function.

First, let's start by observing this recursive tree structure.

So as we can see, here, we have one, two and three levels to this recursive tree structure.

So we can write that out level one, level two, and level three.

And for this first level, here, we're calling the fib function two times.

So one, two, and for this second level, we call our fib function four times 1234.

So this level, we make two calls to the Fibonacci function in this level, we make four calls to the Fibonacci function.

And let's just ignore this third level for now.

And let's just focus on these top two levels.

So two here is the same as two to the power of one and four, here's the same as two to the power of two.

And as you can see, our exponents correlate with our levels.

So actually, if these three functions were to make their two additional calls to recursive Fibonacci, we would have something that looks like this.

So we have two calls here, two calls here, and two calls here.

So we'll just write this out.

So let's imagine that these are also additional costs to the recursive Fibonacci function.

And let's just imagine that that's the case for one second, just so that we can get a better understanding of why this function is of exponential time complexity.

So now, if we count the calls at this third level to our recursive Fibonacci function, and keep in mind that these calls won't actually be made, only these ones will be made.

But we're just writing this out so that we can get a better visualization of what's happening here.

So if we counted out these calls to the Fibonacci function, it would be 12345678.

So we would have eight calls at this third level, and eight is the same as two cube or two to the power of three.

And as you see, once again, our exponent corresponds with our level.

So that means that if our n is four, we would go three levels deep.

And at each level, the number of calls to our Fibonacci function increases exponentially.

But you might be wondering, since our n is four, and we stop here, when it's two to the power of three, as opposed to two to the power of four, how does that result in this function being off to to the end? Well, it's actually quite simple.

So in actuality, this Fibonacci function is O of two to the n minus one.

And if we write this out, you can see it's o of two to the fourth power minus one, which is just equal to O of two to the third power, which is the same as the number of calls made at this third level, right.

And if you remember, in bego, we ignore constants.

So if in actuality, this function is O of two to the nth power minus one, and we ignore the constants, that means that we're going to ignore this minus one, which results in the time complexity of this function being o of two to the N.

And at this point, you're probably wondering how we're able to add these function calls in here.

And in actuality, I only added these function calls in here to give you guys a better visualization of what's happening at each level and why we're considering this function to be off to to the internet.

Because it's easier to visualize if we actually write out these functions that we're actually not calling.

And we can do that because with bego, as we've learned, we're only looking for an upper bound, like we're not looking for a tight bound, we're not looking to be very specific, we're only looking for you can say an estimation of the worst case scenario.

So as you can see here, on this left function, we're calling fib and then we're subtracting one from n.

And on this right one, we're calling fib and then we're subtracting two from n.

So this right side of the tree is always going to be shorter than this left side of the tree, there's always going to be this empty space.

Because on this right side of the tree, at every level, we're subtracting two.

And at this upside of the tree, at every level, we're subtracting one.

But when we're taking bego into consideration, we don't need to worry about this.

And regardless of what number we pass into this function, at the bottom most level, there's always going to be a gap on this right side.

But that's okay, because we're only looking for an upper bound.

So these are just here to help you visualize what is actually happening and why this function is considered to be of exponential growth.

And that is why recursive Fibonacci is of exponential time complexity, I hope that makes sense.

We'll start with the function that will call F.

And this function will be a recursive function.

So this first portion of the code is going to be our base case.

So if the value for n pass to this function is equal to zero, then we're going to print these stars.

And then we're just going to return but if we pass a value to n, that's not equal to zero, then we will go down here to this for loop.

So let's start with an example.

So let's say that we pass the number three to our function, what will happen first is we'll check to see if in which is three in our case is equal to zero, which it's not.

And then we'll move on to this for loop.

And what this for loop is going to do is, for every iteration of in, for every iteration, up until three from zero up until three, which is our end, we're going to recursively call this function again, this time using our n minus one.

So let's, let's try to visualize this.

So if we pass through to this function, and we end up at this for loop, we can write it out like this.

So for each index, up until three, but not including 3012.

And the reason we're only doing for each index 012 is because here, I starts off at zero, and we're going to iterate through our input value in up until AI is no longer less than in.

So once I becomes equal to n, then we'll stop.

So if I were to be three, then we wouldn't go through this loop again.

So that's why it's 012.

And for each of these iterations, 012, we're going to call this function again.

And that's going to look something like this.

So if you look here, we're subtracting one from in that we're passing to the function at each iteration of this for loop.

So if n is three here, for each of these, n is going to be equal to two because we're going to subtract a one for each of these.

So these are actually going to be f two.

And for each of these, we're going to do the same thing that we did for the first call to this function to this f function.

But this time, we'll only iterate through indexes, zero, and one.

So each of these are their own individual calls to this recursive function, right.

And each of these needs to have their own for loop, which is this, this in this.

So at this point, f is two.

So we're iterating up until I is no longer less than two.

So we'll have index zero and one that we're iterating through and for index zero and one, we're going to do this and the same for this call to the recursive function for index zero and one or We're going to do this and the same for this one.

And I apologize if the writing here is getting too small.

But you'll see that this recursive tree gets very large very quickly.

So I'll actually need to shrink this down a little bit.

So that we can have more room.

So for each of these, we're going to call the recursive function again.

But this time, the function is being called with two minus one, which is going to mean that our in is going to be one.

Let's make this a little bit smaller, actually.

And again, I apologize.

So at this point, our for each is only going to happen once for index zero.

Man, this is getting really tiny.

Okay, so at this point, our F is one for all of these calls to the recursive function, and AI starts off as zero.

And as long as i is less than n, which is one, then we'll do this code.

And it's only going to be less than in when it's zero, which is this one iteration.

So for each of these calls to the recursive function, we're only going to call this function once for this first iteration, which is zero.

Now at this point, it's going to be f one minus one.

And f one minus one is actually going to be equal to zero.

So it's going to be f zero.

So we're going to be passing zero as our in to the function.

And it's going to be a little bit difficult to see because it's small.

But if we remember up here, in the actual function, our base case is if n is equal to zero, then we're just going to console log, and then we're going to return.

So for each one of these calls to the recursive function, we're going to perform this code this console log code.

And then after we perform this console log code, we're going to return so it's going to be finished, this entire function will be finished, because all of these are going to return, they're going to log the code, and then they're going to return.

And once all of these return, this entire function is going to be complete, it's going to terminate.

So instead of writing out console log, we'll just write that each of these functions performs log n after the log, the function will return.

So it'll stop.

So for the last time, I'm going to need to make this a little bit smaller.

Alright, so what we're left with when this function is finished is we're left with this tree structure.

And this tree structure shows how many recursive calls that we had to make to get to our base case for each of these recursive calls.

And if you look here, I'll go ahead and circle these so that you can see them more clearly.

If you look here, for each of these recursive calls to the function, we had to perform this code, we had to perform this code here for each of these recursive calls to the function.

So at the final level, where our base case was, we had to perform this code.

And if you count these, you'll see that this is 123456.

So six times we needed to perform this code passing three into our function caused us to need to recall this final recursive call to our function six times and perform this code six times.

And that number six is our key to understanding factorial time complexity, because if you look here, we have oh three factorial.

And the reason why is because our n is three, right? So it's, we're just substituting so all three factorial right and three factors.

Mario is six actually, because to get the factorial of a number, you just multiply every number up until that number.

And if we multiply two times one, we get two.

And if we multiply that two times three, we get six.

And, and again, we needed to execute this console log this code, we need to execute 123456 times.

And if we dig a little deeper, we'll see the three factorial is a result of multiplying every number up until three, which is also the same as multiplying every number from three down until one, which we can see if we look at how it progresses through our tree structure.

Here, we can see the first three is passed.

So first three is passed.

And then three times two is passed three times.

So times three times two is best.

And the result of three times two is six, and six times six times one is past.

So six times 123456 times one is past.

So this for loop first passes to three times, so passes to three times 123, which is the same as 333, times times two, three times 123, passing two.

And when we've asked to to the function, we do two iterations, so three times two iterations.

So we're going to do this, we're going to iterate through this for loop of two iterations, three times three times two, and then three times two is going to be six, because we do two iterations for each of these three.

So this, these iterations plus these iterations, plus these iterations equals six iterations.

And for each of these six iterations, we're going to pass one to the function, so six iterations, so six times will pass one to the function.

So that's here, six times one, six times one, and that is factorial time complexity.

I hope that makes sense.

So to understand space complexity, we'll take this function into consideration.

And this is a recursive function, that basically just returns a call to itself with its input in minus one, it's going to do this until we reach a base case where n equals zero, and then it's going to just return and at that point, this function will be complete.

So let's go ahead and draw with the execution of this function would look like.

So let's say that we passed the number five to this countdown function.

So with this first call to countdown with argument five, we'll end up at this base case.

And we'll see that our n five is not equal to zero.

So we'll move on to this part of the code, which is just calling this function again with five minus one.

And of course, five minus one is going to be four.

And once again, we'll end up here, and we'll call the function again with four minus one.

And we'll continue to do this until we pass zero as our end to the function.

And I will need to make this a little bit smaller.

And finally, we get to the call where we're passing zero as our into the function.

At this point, if n is equal to zero, that function will just return.

So to understand space complexity, it's actually quite simple.

So since this is a recursive function, each one of these calls exists on the call stack simultaneously.

So that means that if we call our countdown function with five, it's going to then call itself with four and at this point, this initial call still exists on the call stack.

And the same for when we call three.

These two calls still exist on the call stack, and all the way down until we reach our base case.

Every single one of these calls still exists on the call stack.

And each one of these calls takes memory.

So each one of these calls existing on the stack, they take up memory.

And this is how we come to an understanding of space complexity using this recursive function as an example, because if we're returning at this point, when we reach our base case, that means that it means that we have 123455 calls taking up space on our call stack, and five also happens to be our value for n.

So that would mean that this function, its space complexity is O of n.

So this function has a space complexity of obon.

So the most important thing to remember here is that all of these recursive calls exist on the call stack simultaneously.

And each one of them takes up memory, which is why, if we have, if we pass in five, two as our n, we'll have five calls existing in memory simultaneously, which means that our space complexity is going to be over then it's going to scale linearly with the size of the input.

So if we increase the size of this input, the space required to execute this function is going to scale proportionally with the size of this input.

So now that we have an understanding of space complexity, we can get into some common mistakes that people make with Bingo.

And the first one being that when you first start out with Viggo, you might see a function that looks like this that has two for loops.

And you might instinctively assume that this function is of all of in square time complexity, because you see that there are two for loops here.

So that must mean observe in square.

But actually, as we've learned O of n square actually means that for each iteration, up until the size of our input, we're going to iterate all the way through an additional for loop up until the size of our input.

So what does it mean if we have two for loops that aren't nested that aren't old in square, it's actually quite simple.

So we have one for loop here, and we have another for loop here.

And as we already know, this for loop would be O of n, time complexity.

And this one would also be O of n.

So this point, we have to all events, so that could easily be translated to o of two in, which is just all of two times in so two times we have all of in.

But if we remember from our previous lessons, we ignore constants.

And in this case, multiplying in by two, two is just a constant.

So we can actually just drop this constant, in which case, this just becomes over then.

But there's one important thing that we need to recognize here.

This is all then because we're iterating through the same input for both of these four loops.

So as long as our loops are acting on the same input, then this would be the resulting complexity.

But there's actually another common mistake that people make when taking time complexity into consideration, which is somewhat related to this mistake.

And this common mistake involves having two separate inputs to the function.

So let's first take this two inputs add function into consideration.

So if you remember from our last example, we only had an input, we only had one input, which was a and the two for loops loop through that same input.

But for this one, you can see that we have two separate inputs here.

So we have an input a, which is loop through in this top four loop.

And we have an input B, which is looped through in this second for loop.

And some people might make the mistake of thinking that this is the same as the last situation where the result would be o of two in.

But this is actually wrong.

Because in this particular situation, we have no way of knowing the difference in size of both of these inputs, like all we know is that these are two separate inputs.

So these two separate inputs could be of either completely different sizes, or they could be of the same size.

But from our analysis perspective, we have no idea.

so in this situation, when we have two inputs, and we have a separate for loop for each input, we're going to need to keep track of both of the inputs.

So in this case, the time that it would take to loop through both these for loops is O of A plus B, because we need to first loop through this one up until we reach the value of a and then we need to loop through this one up until we reach the value of V of B and at this point, this can't be simplified any further we need to acknowledge the fact that both of these inputs are separate inputs.

So this would be over a plus b.

And here we have the similar situation where we have two inputs, but this Time The four loops are nested.

And a lot of people make the mistake of saying that this a function that looks like this is O of n square.

But that would actually be wrong as well, because what does O of n square mean over n square means that for every iteration of one input, we're going to iterate through that same exact input.

But in this situation, when we have a, we have two separate inputs.

For every iteration of one of the inputs, we're going to iterate through the other input.

So what that means is, this is wrong.

In actuality, it's o of A times V, because again, we need to specify that these are two different inputs.

And these inputs could be of different sizes.

And we need to make that visible when we take our complexity into consideration.

So that is space complexity and some common mistakes that people make with big O notation.

I hope that that makes sense.

Time complexity analysis helps us determine how much more time our algorithm needs to solve a bigger problem.

In this article, I will explain what Big O notation means in time complexity analysis. We'll look at three different algorithms for checking if a number is prime, and we'll use Big O notation to analyze the time complexity of these algorithms.

What does Big O Notation Mean?

Big O notation describes how an algorithm's estimated runtime increases when we increase the size of the problem we are solving.

Let's consider some hypothetical algorithms for sorting a list of numbers.

If we have an O(n) algorithm for sorting a list, the amount of time we take increases linearly as we increase the size of our list.

A list that has 10 times as many numbers will take approximately 10 times as long to sort. This means that if sorting 10 numbers takes us 4 seconds, then we would expect sorting a list of 100 numbers to take us approximately 40 seconds.

If we instead have an O(n²) algorithm for sorting a list, then we should expect that the amount of time we take will increase quadratically as we increase the size of our list.

A list that has 10 times as many numbers will take approximately 100 times as long to sort! This means that if sorting 10 numbers takes us 4 seconds, then we would expect sorting a list of 100 numbers to take us approximately 400 seconds.

The fastest algorithms for sorting a list are actually O(n log(n)).
With these algorithms, we can expect that a list with 10 times as many numbers will take approximately 23 times as long to sort.

In other words, if sorting 10 numbers takes us 4 seconds, then we would expect sorting a list of 100 numbers to take us approximately 92 seconds.

Big O Example - Prime Number Checker

Now that we know what Big O notation tells us, let's look at how we use Big O notation in time complexity analysis.

In this section, we will look at three different algorithms for checking if a number is prime. By the definition of a prime number, num is prime if the only numbers that divide evenly into num are 1 and num itself.

Algorithm 1 - Check All Possible Divisors

The simplest algorithm I can think of to check if a number is prime is to check for any divisors other than 1 and num itself.

In the is_prime_all() function below, I try dividing every number between 1 and num into num and check for a remainder.

I wrote this code in Rust so I could use criterion to benchmark the runtime, but time complexity analysis with Big O notation works the same way with every programming language.

If you want to run criterion with this code on your computer, you can find the Rust source code on GitHub.

pub fn is_prime_all(num: i64) -> bool {
    // Check for divisors of num
    for i in 2..num {
        if num % i == 0 {
            // Any divisor other than 1 or num means num is not prime
            return false;
        }
    }
    // No other divisors found means num is prime
    return true;
}

We have to check num - 2 different numbers with this algorithm before we can say that num is prime, so this algorithm has time complexity of O(num) or O(n).

You probably noticed that we removed the -2 from our Big O notation. When we are calculating the time complexity in Big O notation for an algorithm, we only care about the biggest factor of num in our equation, so all smaller terms are removed.

When I tested my function, it took my computer an average of 5.9 microseconds to verify that 1,789 is prime and an average of 60.0 microseconds to verify that 17,903 is prime.

This means that it takes approximately 10 times longer to check a number that is 10 times larger, which we expected from our time complexity analysis!

Algorithm 2 - Check Half of the Possible Divisors

We can improve our algorithm. If our number, num, is not divisible by 2, then we also know that our number can't be divisible by num/2 or any larger number. This means we can check fewer numbers:

pub fn is_prime_half(num: i64) -> bool {
    // Check for divisors of num
    for i in 2..num / 2 {
        if num % i == 0 {
            // Any divisor other than 1 or num means num is not prime
            return false;
        }
    }
    // No other divisors found means num is prime
    return true;
}

This code takes half as long to run. On my computer, it only takes 3.1 microseconds to verify that 1,789 is prime. Unfortunately, it takes 31.1 microseconds to verify that 17,903 is prime, which means that the time complexity of our algorithm did not change!

This is because our largest factor of num was the same in the time complexity of our new algorithm. We need to check num/2 - 1 values, which means that our algorithm is still O(n).

Algorithm 3 - Check all Possible Divisor Pairs

Let's try a third algorithm and see if we can get a smaller time complexity.

For this algorithm, we will improve upon our second algorithm. In algorithm 2, we use the fact that if 2 is not a divisor of our number, num, then num/2 can't be a divisor either.

But this is not a special trick we can only do with 2. If 3 is not a divisor of our number, then num/3 also can't be a divisor. If 4 is not a divisor of our number, then num/4 can't be a divisor either.

The biggest number we need to check is √num, because √num * √num = num.

pub fn is_prime_sqrt(num: i64) -> bool {
    // Check for divisors of num
    for i in 2..=(num as f64).sqrt() as i64 {
        if num % i == 0 {
            // Any divisor other than 1 or num means num is not prime
            return false;
        }
    }
    // No other divisors found means num is prime
    return true;
}

We are only checking √num - 1 different numbers, so this means that our time complexity should be O(√n). When I run this on my computer, I see that it takes only 161.9 nanoseconds to check that 1,789 is prime and 555.0 nanoseconds to check that 17,903 is prime.

This means it took approximately 3.4 times longer to check a number that is 10 times larger, and √10 ≈ 3.2. Our complexity analysis accurately estimates how much longer it takes to check bigger prime numbers with this algorithm.

Summary

Time complexity analysis helps us determine how much more time our algorithm needs to solve a bigger problem.

We looked at what Big O notation means in time complexity analysis, and we used Big O notation to analyze the time complexity of three primality checking algorithms.

In this article we will talk through the most common types of ‘Big O’ notation, using birthday cakes to illustrate the concepts. We'll pretend we're hosting a party, and need to determine how many cakes to bake based on how many people attend.

O(1) - Constant Time

For the Constant Time example, no matter how many people come to the birthday party, you only make one cake. So the cake making time stays constant.

Note that Big O notation doesn’t specify how long the Constant Time is (maybe it takes 1 hour to make the cake, maybe it takes 4 hours). It just states that the time taken doesn’t increase with the number of guests.

A real world example of an O(1) operation is accessing an array by its index. It is just as quick to retrieve an element from a 10 item array as it is to retrieve an element from a 1 million item array.

O(log n) - Logarithmic Time

For the Logarithmic Time example, the birthday cakes are used as a way to incentivise people to turn up to the party on time.

The first person to arrive gets a cake all to themselves. Then the next 2 people to arrive share a cake. Then the next 4 people all share a cake, and so on.

So a 1 person party requires 1 cake. A 2 or 3 person party requires 2 cakes. A 4 - 7 person party requires 3 cakes, and a 8 to 15 person party requires 4 cakes. In general an ‘n’ person party requires log2(n) cakes.

The most common real world example of an O(log n) operation is a binary search of an ordered array.

This algorithm looks at the middle of an array and sees if the value is lower or higher than the one it is looking for. Since the list is ordered, it then knows which half of the array the target value is in.

It then repeats the process with that half of the array. So for a 16 item array, the first iteration narrows down the search to 8 items, then 4 then 2 and then 1, for a maximum of 4, or log2(16), iterations over all.

O(n) - Linear Time

For the Linear Time example, each guest gets their own cake. If ‘n’ people come to the party, you need to make ‘n’ cakes. So the time taken is related to the number of guests.

Again Big O notation doesn’t specify how long the time is (maybe it takes 1 hour to make the cake, maybe it takes 4 hours), it just states that the time increases linearly with the number of guests.

A real world example of an O(n) operation is a naive search for an item in an array. In a 10 item array, at worst you will have to look all 10 items to find the one you want. But for a 1 million item array, you may have to look at all 1 million.

Of course, you might find the solution sooner, but Big O notation specifies the maximum amount of time that an algorithm will take.

O(n^2) - Quadratic Time

For the Quadratic Time example, each guest gets their own cake. Additionally, each cake has the names of all the guests written on it, with some delicious icing.

In this case a 1 person party has one cake with one name on it. A 2 person party has two cakes, both with two names on (4 names total) and a 3 person party has three cakes, all with three names on them, which is 9 names in total.

In general, an ‘n’ person party requires n*n names to be written (also known as n squared, or n to the power of 2), so the speed of making cakes (and writing all the names) is related to the square of the number of guests.

A real world example of an O(n^2) operation is a naive search for duplicates in an array. In this scenario, you loop through all the items in the array, and for each of those items, loop through the array again to see if there are any matches.

For a 10 item array, the outer loop has 10 iterations, and for each of those there are 10 iterations of the inner loop, for 100 in total. For a 1 million item array, it is 1000 billion.

There is a more general case of O(n^2), where instead of the time being relative to n to the power of 2 (n^2), it is relative to n to the power of c (n^c). This is usually called Polynomial Time.

O(n!) - Factorial Time

For the Factorial Time example, the guests take part in a Pétanque competition, and the winner takes home the cake.

There is a slight issue, though, in that the player that takes the first turn is at a disadvantage. To help level things out, many games are played, so that each permutation of guests is covered and everyone gets to go first. All these permutations are written on to the cake, again with some tasty icing.

This means that a 2 person party has two games, as each guest takes it in turn to go first. A 3 person party has 6 games (if we imagine that the guests are Anna, Brian and Chris, then the permutations are ABC, ACB, BAC, BCA, CAB, CBA).

In general, an ‘n’ person party requires n!, or n factorial games, so the speed of making the cake is related to the this.

n! is calculated by multiplying all whole numbers from n down to one “n (n - 1) (n - 2) … 2 1”. So for the 2 person party it is 2 1, or 2. For the three person party it is 3 2 * 1, which is 6.

Real world examples of O(n!) operations are anything that requires analysing a list of permutations, such as the traveling salesman problem.

Conclusions

Hopefully the birthday cakes have made ‘Big O’ notation easier to digest! The graph below is also a good memory aid, showing the relative speeds of the algorithms (if there is a choice, then you want the faster one!)

There are quite a few other ‘Big O’ notations, such as O(n log n) and O(c^n) but they all follow the same pattern. If you want to learn more about it, check out this article.

Trade-offs are present in all our activities. Maybe you have heard the so-called "No free lunch theorem" in Machine Learning. The theorem states that there is no silver bullet when it comes to machine learning models. But in fact, there is never a silver bullet when it comes to anything.

And that is not a Computer Science principle but an economics principle.

If you have written code for more than a month you have likely experienced the necessity of trade-offs in programming – or at least have heard about them.

Sometimes you sacrifice performance in the name of security, security in the name of scalability, beauty and readability in the name of performance, and so on. Don't forget you also probably sacrifice parties and fun in general in the name of programming, so make it worth it.

In the specific case of algorithms, the main resources are time and memory, so the trade-offs always involve those resources.

It's common to find several solutions for the same problem, because one of them is faster but the other one is cheaper when it comes to storage. And of course, there are other factors like implementation, simplicity, and security.

In this post, I'm going to write about how you can combine several solutions to get the one that fulfills all your requirements.

First I'm going to show an interesting idea that E.W. Dijkstra proposed to find prime numbers. After that, I will show an idea I came up with to obtain a data structure that combines the power of arrays and linked lists.

Requirements

I assume you have basic programming skills as well as some knowledge about data structures like arrays, linked lists, and heaps.

You should also have some understanding of big-O notation to calculate complexity.

Lastly, it would be good you were familiar with the algorithm called tje Sieve of Eratosthenes. In case you aren't, you can check out this post link.

There is no other previous knowledge required to understand what I'm about to discuss.

Two algorithms, one problem

The problem is to find all prime numbers from 0 (zero) to N. It's the kind of problem you learn to do when you are beginning your journey in programming. And I want to start with the simplest solution.

The Naive Algorithm

In the naive algorithm, we iterate over all numbers x from 2 to N. Then we check whether x has any divisor besides itself and one. For the last step, we can check for every number d between 2 and x - 1 whether it is a divisor or not.

There is room for improvement in the last step, because we only need to check the divisors that are less than or equal to the square root of x. A pseudocode of the algorithm is written below:

   primes(N):
      prime_numbers <- [] # empty list
      for x = 2 to N:
          is_prime <- true
          for d = 2 to sqrt(x):
              if d divides x:
                   is_prime <- false # we found a divisor of x so x is not a prime number
          if is_prime:
               prime_numbers.add(x) # if we didn't find a divisor then x is prime
       return prime_numbers

What's the runtime complexity of the previous algorithm? Well, we take every number from 2 to N and for each one, we iterate over all its possible divisors. So we make O(N*sqrt(N)) operations, where sqrt stands for the square root function.

What about memory? We only store the primes we find. For a big enough N, the number of primes is relatively small compared with N. So, let's denote the memory complexity as O(Primes(N)), where Primes(N) is the number of primes between 0 and N. Note that this is optimum in terms of memory because we at least need to store all the prime numbers.

The Sieve of Eratosthenes

You probably already know that there is a better algorithm to find all the prime numbers in a given range: the sieve of Eratosthenes. Let's look at it.

The idea is to maintain an array of length N where every entry is either false or true. If the i-th position in the array is true, then we say that i is a prime number, otherwise i is not prime.

We start with all positions with a true value, and then for every position, starting with i = 2, we make false every multiple of i.

We end up with an array in which every position with a true value represents a prime number. The code with some optimizations is presented below.

    primes(N):
        prime_numbers <- [] # empty list
        sieve <- a boolean list with length equal to N and all its elements set to true

        for i = 2 to sqrt(N): # we only need to analyze the numbers less than or equal to sqrt(N)
            if sieve[i]: # if sieve[i] is true then i is prime
                prime_numbers.add(i)
                for j = i*i to N: # we can start the inner loop in i*i
                    sieve[j] <- false
                    j <- j + i
         return prime_numbers

It can be proved that the algorithm described above does O(N log(N)) operations which is better than the naive approach.

Even it can be improved to O(N)! But we need to store an array with all the N numbers, and thus, we end up with a more expensive algorithm in memory terms. Here we have the trade-off: time in exchange for memory.

Can we design an algorithm that is faster than the naive idea but cheaper in memory terms than the sieve of Eratosthenes?

Dijkstra and the production line

In the '60s, E.W. Dijkstra wrote in one of his manuscripts [PDF] an algorithm that combines the naive and the sieve ideas. But before we talk about it, let's analyze the differences between the two previous algorithms.

When applying the naive algorithm we focus on analyzing whether every number is prime or not. When applying the sieve we analyze, for every prime number, all its multiples. The difference can be illustrated with the following analogy.

Imagine we want to build several products, like action figures. We have two options: building them one by one or applying a production line and in every stage, we add one component of the action figure. With the latter, we end up producing more in less time, but we need the "line infrastructure".

Dijkstra combined those ideas by analyzing a number at a time but taking advantage of the previous operations. We can maintain a pool of primes that have already been discovered, and, for each of those prime numbers, store the smallest multiple that has not been analyzed yet.

For example:

If we are analyzing the number 6, then we have stored primes 2, 3, and 5, along with their smallest-not-analyzed-multiples that are: 6 for 2, also 6 for 3, and 10 for 5.

Then, when analyzing a new number we take the smallest multiple stored until that moment and if that multiple is greater than the new number, then we have found a new prime. Otherwise, we have a composite number and we need to update the multiples of the stored primes that have the new number as its smallest multiple.

We begin storing the prime number 2 with the smallest multiple 4 as well. Then when analyzing 3 we find that 4 > 3 so 3 is prime. We store 3 along with its smallest multiple that has not been analyzed yet (6). When analyzing 4 we find that 4 is stored as a multiple of 2, then we update the multiple of 2 that now will be 6. When analyzing 5 we find that 6 > 5 so 5 is a prime number and we store it along with 10, and so on... The code is presented below.

    primes(N):
        primes_pool <- Heap( (4, 2) ) # a heap that contains a tuple with a prime number (2) and its least multiple that hasn't been analyzed yet (4).
        prime_numbers <- [2] # a list that contains the number 2
        for i = 3 to N:
            tuple <- getMin(primes_pool) # get the tuple with the minimum multiple, the prime number attached to it is irrelevant
            mult <- tuple.first # the multiple is stored in the first position of the tuple
            if mult > i:
                prime_numbers.add(i) # i is prime!
                primes_pool.insert( (i*i, i) ) # we insert i along with their least multiple, but it can be inserted i*i instead and the algorithm remains correct
                continue
            # otherwise i isn't prime and then...
            for t such that t is in primes_pool and t.first is equal to mult:
                t.first <- t.first + t.second # we update every tuple in the pool that has i as it's least multiple
        return prime_numbers

The previous method only stores the prime numbers and another number for each of those primes. So we have a memory complexity of O(Primes(N)) which is the same as the naive idea.

If we store the prime numbers along with their multiples in a structure like a heap, we get a time complexity of O(N*log N) which is the same as the sieve. So we got what we wanted!

The trick here is that we don't need to mark every multiple of the given prime but just the smallest multiple.

I need to say that this is not a practical idea in the sense that the memory complexity of the sieve of Eratosthenes is not that bad and it is an algorithm that's very easy to implement.

My point is that sometimes, if you have several ideas, each of which cannot be applied because of some flaw, then maybe is a good idea to combine their strengths. This gives you a hybrid solution for your problem.

Dijkstra's Factory of Primes taught me to think that way, although I have never implemented that algorithm in a real-life scenario.

Combining arrays with linked lists

Arrays are simple structures that allow us to get an element by its index in constant time. But we need O(N) operations to insert or remove an element to/from the array in the worst case, where N is the length of the array.

On the other hand, linked lists are structures composed of nodes. Every node has a reference to the next one, and, in the case of doubly-linked lists, each node also has a reference to the previous one.

In this case, we need O(N) operations to reach a node in the worst case, but the insert and remove operations can be done in constant time.

I think it's natural to think about a "perfect data structure" that allows us to make the three operations in constant time. Sadly, such a structure does not exist, but I have found a middle point between the two opposite poles.

The "issue" with arrays is that they maintain a reference to all of their elements. That allows us to retrieve any element with the same amount of operations no matter where the element is.

But maintaining those references is what makes the insertions and deletions so costly.

When it comes to linked lists we only maintain a reference to the first and the last node and each node has a reference to its neighbors. So, when inserting or removing a new element we only need to change a few references.

But that lack of references is the reason that we have to spend so many operations to get an element in the worst case.

Viewing the problem from that angle, the idea of finding a middle point in the number of references seems natural. What happens if we maintain a reference to sqrt(N) nodes of the linked list instead of referencing just the first and the last element?

That allows us to have a list of length sqrt(N) such that the distance between each of those nodes in the actual list is sqrt(N). Having that, we can do each operation (index, insertion, and deletion) in O(sqrt(N)).

If you want to see more details about this structure and a Lisp implementation of it, you can do it here.

I have also written a post about it in my personal blog.

Conclusions

We have seen two examples of how you can combine existing solutions to get another one that has some of the good qualities of each of them. My purpose was to show you this way of thinking, not just specific examples.

Note that in the case of Dijkstra's idea, we could achieve the time of the fastest solution and the memory complexity of the naive algorithm. In the second example, we just got a middle point, so the fastest solution is still faster and the memory-cheaper solution is still cheaper.

But the new structure is like a decathlon athlete – it is good in every specificity, but not the best in any one of them.

So don't try to find the silver bullet – remember that there's no free lunch. Even Dijkstra's idea has the disadvantage of being harder to implement and to understand.

Hope you have learned something from this post. You can find more content like this in my personal blog and by following me on Twitter.

What is Big O notation and how does it work?

Simply put, Big O notation tells you the number of operations an algorithm will make. It gets its name from the literal "Big O" in front of the estimated number of operations.

What Big O notation doesn't tell you is the speed of the algorithm in seconds. There are way too many factors that influence the time an algorithm takes to run. Instead, you'll use Big O notation to compare different algorithms by the number of operations they make.

Big O establishes a worst-case run time

Imagine that you're a teacher with a student named Jane. You want to find her records, so you use a simple search algorithm to go through your school district's database.

You know that simple search takes O(n) times to run. This means that, in the worst case, you'll have to search through every single record (represented by n) to find Jane's.

But when you run the simple search, you find that Jane's records are the very first entry in the database. You don't have to look at every entry – you found it on your first try.

Did this algorithm take O(n) time? Or did it take O(1) time because you found Jane's records on the first try?

In this case, 0(1) is the best-case scenario – you were lucky that Jane's records were at the top. But Big O notation focuses on the worst-case scenario, which is 0(n) for simple search. It’s a reassurance that simple search will never be slower than O(n) time.

Algorithm running times grow at different rates

Assume that it takes 1 millisecond to check each element in the school district's database.

With simple search, if you have to check 10 entries, it will take 10 ms to run. But with the binary search algorithm, you only have to check 3 elements, which takes 3 ms to run.

In most cases, the list or database you need to search will have hundreds or thousands of elements.

If there are 1 billion elements, using simple search will take up to 1 billion ms, or 11 days. On the other hand, using binary search will take just 32 ms in the worst-case scenario:

Clearly the run times for simple search and binary search don't grow at nearly the same rate. As the list of entries gets larger, binary search takes just a little more time to run. Simple search's run time grows exponentially as the list of entries increases.

This is why knowing how the running time increases in relation to a list size is so important. And this is exactly where Big O notation is so useful.

Big O notation shows the number of operations

As mentioned above, Big O notation doesn't show the time an algorithm will run. Instead, it shows the number of operations it will perform. It tells you how fast an algorithm grows and lets you compare it with others.

Here are some common algorithms and their run times in Big O notation:

Now you know enough to be dangerous with Big O notation. Get out there and start comparing algorithms.

Do you really understand Big O? If so, then this will refresh your understanding before an interview. If not, don’t worry — come and join us for some endeavors in computer science.

If you have taken some algorithm related courses, you’ve probably heard of the term Big O notation. If you haven’t, we will go over it here, and then get a deeper understanding of what it really is.

Big O notation is one of the most fundamental tools for computer scientists to analyze the cost of an algorithm. It is a good practice for software engineers to understand in-depth as well.

This article is written with the assumption that you have already tackled some code. Also, some in-depth material also requires high-school math fundamentals, and therefore can be a bit less comfortable to total beginners. But if you are ready, let’s get started!

In this article, we will have an in-depth discussion about Big O notation. We will start with an example algorithm to open up our understanding. Then, we will go into the mathematics a little bit to have a formal understanding. After that we will go over some common variations of Big O notation. In the end, we will discuss some of the limitations of Big O in a practical scenario. A table of contents can be found below.

Table of Contents

1. What is Big O notation, and why does it matter
2. Formal Definition of Big O notation
3. Big O, Little O, Omega & Theta
4. Complexity Comparison Between Typical Big Os
5. Time & Space Complexity
6. Best, Average, Worst, Expected Complexity
7. Why Big O doesn’t matter
8. In the end…

So let’s get started.

1. What is Big O Notation, and why does it matter

“Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation.”

— Wikipedia’s definition of Big O notation

In plain words, Big O notation describes the complexity of your code using algebraic terms.

To understand what Big O notation is, we can take a look at a typical example, O(n²), which is usually pronounced “Big O squared”. The letter “n” here represents the input size, and the function “g(n) = n²” inside the “O()” gives us an idea of how complex the algorithm is with respect to the input size.

A typical algorithm that has the complexity of O(n²) would be the selection sort algorithm. Selection sort is a sorting algorithm that iterates through the list to ensure every element at index i is the ith smallest/largest element of the list. The CODEPEN below gives a visual example of it.

The algorithm can be described by the following code. In order to make sure the ith element is the ith smallest element in the list, this algorithm first iterates through the list with a for loop. Then for every element it uses another for loop to find the smallest element in the remaining part of the list.

SelectionSort(List) {
  for(i from 0 to List.Length) {
    SmallestElement = List[i]
    for(j from i to List.Length) {
      if(SmallestElement > List[j]) {
        SmallestElement = List[j]
      }
    }
    Swap(List[i], SmallestElement)
  }
}

In this scenario, we consider the variable List as the input, thus input size n is the number of elements inside List. Assume the if statement, and the value assignment bounded by the if statement, takes constant time. Then we can find the big O notation for the SelectionSort function by analyzing how many times the statements are executed.

First the inner for loop runs the statements inside n times. And then after i is incremented, the inner for loop runs for n-1 times… …until it runs once, then both of the for loops reach their terminating conditions.

Selection Sort Loops Illustrated

This actually ends up giving us a geometric sum, and with some high-school math we would find that the inner loop will repeat for 1+2 … + n times, which equals n(n-1)/2 times. If we multiply this out, we will end up getting n²/2-n/2.

When we calculate big O notation, we only care about the dominant terms, and we do not care about the coefficients. Thus we take the n² as our final big O. We write it as O(n²), which again is pronounced “Big O squared”.

Now you may be wondering, what is this “dominant term” all about? And why do we not care about the coefficients? Don’t worry, we will go over them one by one. It may be a little bit hard to understand at the beginning, but it will all make a lot more sense as you read through the next section.

2. Formal Definition of Big O notation

Once upon a time there was an Indian king who wanted to reward a wise man for his excellence. The wise man asked for nothing but some wheat that would fill up a chess board.

But here were his rules: in the first tile he wants 1 grain of wheat, then 2 on the second tile, then 4 on the next one…each tile on the chess board needed to be filled by double the amount of grains as the previous one. The naïve king agreed without hesitation, thinking it would be a trivial demand to fulfill, until he actually went on and tried it…

_Wheat and Chess Board, Image from Wikipedia_

So how many grains of wheat does the king owe the wise man? We know that a chess board has 8 squares by 8 squares, which totals 64 tiles. So the last tile should have a total of 2⁶³ grains of wheat. If you do a calculation online, for the entire chessboard, you will end up getting 1.8446744*10¹⁹ – that is about 18 followed by 18 zeroes.

Assuming that each grain of wheat weights 0.01 grams, that gives us 184,467,440,737 tons of wheat. And 184 billion tons is quite a lot, isn’t it?

The numbers grow quite fast later for exponential growth don’t they? The same logic goes for computer algorithms. If the required efforts to accomplish a task grow exponentially with respect to the input size, it can end up becoming enormously large.

As we will see in a moment, the growth of 2ⁿ is much faster than n². Now, with n = 64, the square of 64 is 4096. If you add that number to 2⁶⁴, it will be lost outside the significant digits.

This is why, when we look at the growth rate, we only care about the dominant terms. And since we want to analyze the growth with respect to the input size, the coefficients which only multiply the number rather than growing with the input size do not contain useful information.

Below is the formal definition of Big O:

[CSE 373 Slides](https://slideplayer.com/slide/9739625/" rel="noopener) from University of Washington

The formal definition is useful when you need to perform a math proof. For example, the time complexity for selection sort can be defined by the function f(n) = n²/2-n/2 as we have discussed in the previous section.

If we allow our function g(n) to be n², we can find a constant c = 1, and a N₀ = 0, and so long as N > N₀, N² will always be greater than N²/2-N/2. We can easily prove this by subtracting N²/2 from both functions, then we can easily see N²/2 > -N/2 to be true when N > 0. Therefore, we can come up with the conclusion that f(n) = O(n²), in the other selection sort is “big O squared”.

You might have noticed a little trick here. That is, if you make g(n) grow super fast, way faster than anything, O(g(n)) will always be great enough. For example, for any polynomial function, you can always be right by saying that they are O(2ⁿ) because 2ⁿ will eventually outgrow any polynomials.

Mathematically, you are right, but generally when we talk about Big O, we want to know the tight bound of the function. You will understand this more as you read through the next section.

But before we go, let’s test your understanding with the following question. The answer will be found in later sections so it won’t be a throw away.

Question: An image is represented by a 2D array of pixels. If you use a nested for loop to iterate through every pixel (that is, you have a for loop going through all the columns, then another for loop inside to go through all the rows), what is the time complexity of the algorithm when the image is considered as the input?

3. Big O, Little O, Omega & Theta

Big O: “f(n) is O(g(n))” iff for some constants c and N₀, f(N) ≤ cg(N) for all N > N₀

Omega: “f(n) is Ω(g(n))” iff for some constants c and N₀, f(N) ≥ cg(N) for all N > N₀

Theta: “f(n) is Θ(g(n))” iff f(n) is O(g(n)) and f(n) is Ω(g(n))

Little O: “f(n) is o(g(n))” iff f(n) is O(g(n)) and f(n) is not Θ(g(n))

—Formal Definition of Big O, Omega, Theta and Little O

In plain words:

• Big O (O()) describes the upper bound of the complexity.
• Omega (Ω()) describes the lower bound of the complexity.
• Theta (Θ()) describes the exact bound of the complexity.
• Little O (o()) describes the upper bound excluding the exact bound.

Relationships between Big O, Little O, Omega & Theta Illustrated

For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

Another way to look at Big O, Image from [Stack Overflow](https://stackoverflow.com/questions/1364444/difference-between-big-o-and-little-o-notation" rel="noopener)

But which function grows faster than the others? There are actually quite a few rules.

Complexity Growth Illustration from [Big O Cheatsheet](http://bigocheatsheet.com/" rel="noopener)

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the least complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

Question: Rank following functions from the most complex to the least complex.

Examples taken from [Textbook Problems](https://www.chegg.com/homework-help/questions-and-answers/problem-ask-refresh-knowledge-asymptotic-notations-rank-following-functions-order-growth-f-q23698273" rel="noopener)

Solution to Section 2 Question:

It was actually meant to be a trick question to test your understanding. The question tries to make you answer O(n²) because there is a nested for loop. However, n is supposed to be the input size. Since the image array is the input, and every pixel was iterated through only once, the answer is actually O(n). The next section will go over more examples like this one.

5. Time & Space Complexity

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

Bucket Sort Visualization

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is smaller than its previous element, it inserts the element backwards until it is larger than the previous element.

_Insertion Sort Illustrated, Image from [Wikipedia](https://en.wikipedia.org/wiki/Insertion_sort" rel="noopener" target="blank" title=")

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their *worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

[Big O Cheatsheet](http://bigocheatsheet.com/" rel="noopener) for Common Algorithms

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to least complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

The factorials can be represented by multiplications, and thus can be converted to additions outside the logarithmic function. The “n choose 2” can be converted into a polynomial with a cubic term being the largest.

And finally, we can rank the functions from the most complex to the least complex.

Why BigO doesn’t matter

!!! — WARNING — !!!

Contents discussed here are generally not accepted by most programmers in the world. Discuss it at your own risk in an interview. People actually blogged about how they failed their Google interviews because they questioned the authority, like here.

!!! — WARNING — !!!

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

Time Comparison between Quick Sort & Merge Sort

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

Time Ratio between Quick Sort & Merge Sort

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.

Hope you have a great time learning computer science!!!

If a running time is Ω(f(n)), then for large enough n, the running time is at least k⋅f(n) for some constant k. Here’s how to think of a running time that is Ω(f(n)):

We say that the running time is “big-Ω of f(n).” We use big-Ω notation for asymptotic lower bounds, since it bounds the growth of the running time from below for large enough input sizes.

Difference between Big O and Big Ω

The difference between Big O notation and Big Ω notation is that Big O is used to describe the worst case running time for an algorithm. But, Big Ω notation, on the other hand, is used to describe the best case running time for a given algorithm.

More Information:

• Big-Ω (Big-Omega) notation