Intro to Big O

Colt Steele
A free video tutorial from Colt Steele
Developer and Bootcamp Instructor
4.6 instructor rating • 9 courses • 791,944 students

Learn more from the full course

JavaScript Algorithms and Data Structures Masterclass

The Missing Computer Science and Coding Interview Bootcamp

21:44:06 of on-demand video • Updated November 2018

  • Learn everything you need to ace difficult coding interviews
  • Master dozens of popular algorithms, including 6 sorting algorithms!
  • Implement 10+ data structures from scratch
  • Improve your problem solving skills and become a stronger developer
English [Auto] Hey welcome back. So this is the first real section of the course and we're kicking it off as something really important thing big. It's called Big O notation. And when I say big I don't mean that it's long or difficult even it's big in significance. It's something that we basically I had no choice but to start the course off with this topic because at least if I wanted to make it a good course because it's going to come up in I don't I won't say every single video but maybe 70 percent of the videos and the rest of the course don't hold me to that but a lot of video is a significant number. We're going to refer back to what we talked about in this section. So before I even explain what it is I have a quick warning. There's a bit of math in this section and I'm warning you not to scare you away but actually to encourage you to push through it. If you do struggle with math or if you're someone who hasn't heard the word logarithm ever or in ten or 20 years that's going to come up in this section at the end. But don't panic because what we're going to do here in this section is establish a framework for talking about code and the rest of the course. And that does involve some math upfront but it means that the rest of the Course isn't going to be some of it will be mathy definitely but it's not. This is not indicative of what the rest of the Course will look like. So just push through it if I mean if you like math great if you have some problems with this section just remember that the entire course isn't like this and we're just getting it out of the way because like I said it has to come first. I don't really have a choice. OK. Sorry if I scared anybody there. Let's talk about the objectives for this section. So in this video we're going to start by just talking about the need for something like Big O notation I haven't even mentioned what it is. So we're going to get to that then we're going to describe what it is so why we care about it what it is we're going to learn to simplify Big O expressions we'll define time complexity and space complexity will evaluate time complexity and space complexity of different algorithms using Big O notation and then we'll describe what a logarithm is a bit of math at the end there. So I know it's a lot but we're going to start with this first bullet point motivate the need for something like Big-O notation. So what is the idea here. Well this course is about algorithms it's about solving challenges it's about computer science and data structures. But for every topic in this course there's 10 20 different implementations or solutions that could work probably way more. How do we know what's best. So let's scale it down a bit just to a single problem. Let's say that there are two valid solutions to a problem. They both work and they're different not just in names or variable names or something but totally different in approaches one uses a loop the other uses. I don't know a list or a string or something to accomplish the same task. How do we know which one is best. That's really what Big O is about. It's a system it's a way of generalizing code and talking about it and comparing code and its performance to other pieces of code. Ok so here is a more concrete example. Write a function that accepts a string input and returns or reversed copy. If I asked you to do this which maybe some enterprising students will do this and come up with some creative solutions off the top of my head I can come up with three ish solutions different approaches and I'm sure there are way more out there. I actually found this post on Stack Overflow that has 10 different implementations and Javascript and they're all different. Like I said it's not just a different variable name. It's not just switching a for loop for a while loop. There are different approaches. How do we know if all these work. And here's one using a for loop and an array. Here's one that uses no loops and it's no arrays it's all actually just or is an array and there at one point but it's all built in methods. How do we know which one is best. Well we'll get there. But wouldn't it be nice if there was sort of a system for classifying code or for comparing it which I've already spoiled it and said that's a big O sort of is it sort of like if we're talking about earthquakes. This was a seismology 101 class very early on I would start off by talking about the Richter scale because then that allows us to talk about earthquakes and compare them to one another. So that instead of just saying oh there's a big earthquake and then a bigger one over there. We can say there is a 7.5 and then a 9.2 over there. And that puts things into context. That's kind of not a great analogy but the idea is that we can assign labels generalized labels to our code. So instead of saying something like great or are awful for our code we can have a numeric representation of the performance of code. So that's what big-O is going to give us rather than colors and text like. Great. It's going to look a little bit different. It might look a little mathy but it's actually pretty straightforward. Once you get past the first hurdle of it looking very foreign and weird. So one last point I want to make some of you might be wondering if I asked you to write a function that reverse a string and you get it to work. It doesn't it only matters that you get it to work. Why does it matter what's best the solution you come up with is the best. And in some ways I think that depending on your project and the context that's true the best solution is the one that you can get to work. But when we're talking about things like interviewing technical interview code challenges or working at a large company where you're working with a huge data set let's say hundreds of millions of pieces of data where one algorithm implementation could save an hour every time it runs compared to another implementation. Performance matters at that point and there is an actual best algorithm or best solution. So it's important to have a precise vocabulary to talk about how our code performs. So even if you're content with your solution to something it's helpful to be able to understand how it compares how it performs compared to others. It's also good for discussing tradeoffs between different approaches because often it's not as cut and dry as I made it seem it's not that one solution is always great and the other one is always terrible. Sometimes one solution might be great at handling really large data sets of pieces of data. Another one might always be very consistent in the time that it takes but it might take more time up front. There's tradeoffs so it's not always just. This is the best Also if you're trying to debug your code. It helps to understand things that are slowing it down not just looking for errors. Well let's say that your code is working but for some reason it's taking a lot longer than you expect. Or your computer is lagging and freaking out in the browser when you execute some function. It helps if you understand some of the things we're going to talk about in this section and Big O notation you can actually pinpoint where some problems might arise. So it helps us identify inefficient points and then finally you should care because it comes up in interviews a lot a lot of times an interviewer will say something like tell me the big O of this algorithm or this function that you've written or here's three functions what's the big show that will make sense in a bit but it's important just to know for interviews I said it's less important because hopefully you're learning it to actually understand things and to help you understand your code better and talk about your code better rather than just directly trying to master it for an interview. But interviews are important so no judgment there either. So I'm going to leave this video off here and try to keep things more compact. I don't want any rambling videos. And the next video we're going to pick up with a real example some code and start to analyze how efficient it is.