# Big O Notation

Hi, I’m Gayle Laakmann McDowell, author of Cracking the Coding Interview. Today we’re going to cover one of my favorite topics,

which is big O, or algorithmic efficiency. I’m going to start off with a

story. Back in 2009 there was this company in South Africa and they had

really slow internet they were really really frustrated by, and they actually had

two offices about 50 miles away, so they set up this little test to see if it

would be faster to transfer big chunks of data over the internet with their

really slow internet service provider or via carrier pigeon. Literally they took a bunch of USB

sticks or probably actually one giant one strapped it to a pigeon and flew it

from one office to the next, and they got a ton of press over this test and media

kind of love this stuff right. And of course the pigeon won right. It wouldn’t

be a funny story otherwise. And so they got a whole bunch of press over,

and people are like oh my god I can’t believe that a pigeon beat the internet.

But the problem was it was really actually kind of a ridiculous test because

here’s the thing. Transferring data over the Internet

takes longer and longer and longer with how much data there is. With certain

simplifications and assumptions, that’s not really the case with pigeons. Pigeons

might be really slow or fast but it always basically takes the same amount

of time for a pigeon to transfer one, transfer some chunk of data from one

office to the next. It just has to fly 50 miles. It’s not going to take longer

because that USB stick contains more data, so of course for a sufficiently large

file the pigeon’s going to win. So in big O, the way we talk about this is we

describe the pigeon transfer speed as O of 1, its constant time with

respect to the size of the input. It doesn’t take longer with more input.

Again with certain simplifications and assumptions about the pigeons ability to

carry a USB stick. But the internet time is internet transfer time is O of n. It

scales linearly with respect to the amount of input. Twice amount of data is

going to take roughly twice as much time. So that’s what Big O is. Big O is

essentially an equation that describes how the runtime scales with respect to some input

variables. So I’m going to talk about four specific roles, but first let me show you

what this might look like in code. So let’s consider this simple function that

just walks through an array and checks if it contains a particular value. So you

would describe this is O of n, where n is the size of the array. What about this method that walks

through an array and prints all pairs of values in the array? Note that this will

print if it has the elements 5 and 2 in the array it’ll print both 2 comma 5 and

5 comma 2. So you describe this probably as of O of n squared and where n is the size of the array. You can see that because it has n

elements in the array, so it has n squared pairs, so the amount of time

it’s going to take you to run that function is going to increase with

respect to n squared. Ok so that’s kind of basics of Big O. Let’s take another real-world example. How would you describe the run time to

mow a square plot of land? So a square plot of grass. So you have this plot of

grass and you need to mow all of it. What’s the runtime of this? Well it’s

kind of an interesting question, but you could describe it one of two ways. One of

which, one way you can describe it is O of a where a is the amount of area in

that plot of land. Remember that this is just an equation that expresses how the

time increases so you don’t have to use n in your equation, you can use other

variables and often it make sense to do that. So you just described this as O of

a where a is that the amount of area there. You could also describe this as

O of s squared where s is the amount of, is this length of one side,

because it is a square plot of land so the amount of area is s squared. So it’s

important that you realize that there’s O of a, and O of s squared are obviously saying essentially the same thing, just like when you describe the area of a square. Well you could describe it as 25 or you

describe it as 5 squared, just because it has a square in it doesn’t make it bigger.

So both are valid ways of describing the runtime. It

just depends on what might be clearer for that problem. So with that said, let me go on to 4 important rules to know with the big O. The first one is if you have two different

steps in your algorithm, you add up those steps, so if you have a first step that

takes O of a time and a second step that takes O of b you would add up

those run times and you get O of a plus b. So for example you have this runtime

that, you have this algorithm, that first walks through one array, and then it walks

the other array. It’s going to be the amount of time it takes to walk through each of

them. So you’ll add up their runtimes. The second way, the second rule is that

you drop constants. So let’s look at these two different ways that you can print out the min and max element in an array. One finds the min element

and then finds the max element, the other one finds the min and the max simultaneously.

Now these are fundamentally doing the same thing, they’re doing essentially the

exact same operations, just doing them in slightly different orders. Both of these

get described as O of n, where n is the size of the array. Now it’s really

tempting for people to sometimes see two different loops and describe it as O of 2n

and so it’s important that you remember that you drop constants in big O. You

do not describe things as O of 2n or O of 3n because you’re just looking for how

things scale roughly. Is it a linear relationship, is it a quadratic

relationship, so you always drop constants. The third rule is that if you

have different inputs you’re usually going to use different variables to

represent them. So let’s take this example where we have two arrays and

we’re walking through them to figure out the number of elements in common

between the two arrays. Some people mistakenly call this O of n squared but that’s not correct. When you just talk about runtime if you

describe things as O of n or O of n squared or O of n log n, n must have a meaning,

it’s not like things are inherently one or other. So when you described this as

O of n squared it really doesn’t make sense because it doesn’t,

what does n mean? n is not the size of the array, if there’s two

different arrays. What you want to describe instead is O of a times b. Again

fundamentally, big O is an equation that expresses how the runtime changes, how

its scales, so you describe this as O of a times b. The fourth rule is that you drop

non-dominant terms. So let’s suppose you have this code here that walks through

an array and prints out the biggest element and then for some reason it goes and

prints all pairs of values in the array. So that first step takes O of n time,

the second step takes O of n squared time, so you could first get as a

less simplified form, you could describe this as O of n + n squared, but

note that, compare this to O of n and the runtime, or compare this to the

runtime of O of n squared, and the runtime of O of n squared plus n squared. Both of

those two runtimes reduce down to n squared and what’s interesting here is

that O of n plus n squared, should logically be between them. So this n squared thing

kind of dominates this O of n thing, and so you drop that non dominant term. It’s

the n squared that’s really going to drive how the runtime changes. And if you

want you can look up a more academic explanation for when exactly you drop

things and when exactly you can’t, but this is kinda layman’s explanation for

it. We’ve now covered the very basic pieces

of big O. This is an incredibly important concept to master for your

interviews so don’t be lazy here, make sure you really really understand this

and try a whole bunch of exercises to solidify your understanding. Good luck.

So Big O is not a rapper?

but the time to complete the mowing would have a codependent variable, the mower. The difference between a manual mower and a driven one would make a difference in efficiency, but even more simply, the width of the lawn mower. a lawn mower that is 1 foot wide would take twice as long as one that is 2 feet wide. so isnt it more like O(log N)?

Straightforward. Easy to understand. Cool graphics! Hats off =)

Link: http://vnurl.net/drWCgZEOQ6

Thanks so much, this 8 minute video made it way more clear than several hours of lectures and readings

Wow, Thank you sooo much!

This video helped me a lot for studying for my finals.

Isn't points 1 and 2 self contradictory?

🤔🤔🤔

you lowers your voice in the end of a sentence which is annoying . please try get rid of that .

Great video, thank you. However the font and colors makes the code much harder to read, and therefore to follow without pausing the video.

thought big O was just a great time with a freind

Wait so is Big O the function for runtime, or the speed of runtime increase (the derivative of runtime)?

I hear South Africa.I give a like

Can i define big O as an algorithm

nice examples thank you

A very concise and to-the-point video. Thanks!

Great explanation of Big(O). This is important for any programmer to understand the efficiency of the algorithm.

I know many excellent programmers who don't have CS degrees and may not know the academic description of Big(O). But they know it intuitively through experience. Having said that Bg(O) is an easy concept to understand, requires practice to know how to assess efficiency and scalability of the code.

How do you practice this on your own?

Can I apply this to things I do daily?

What.

This makes me realize Colt Steele's a legend. I came here after watching his tuts on big O and I was surprised at how much I already knew

Excellent! Thanks

the link in the description goes to a 404 page

girl!!! You are so beautiful!!

THIS WAS BEAUTIFULLY SAID HELPED KILLED 2 BIRDS WITH ONE STONE (APPLIED TO BOTH MY CS COURSES) THANK YOU GENIUS!

As mentioned in the book "Cracking the coding interview" chapter Big O, Can anyone please explain the below statement:

"Industry meaning of Big O is closer to what academics mean by 'theta', in that it would be seen as incorrect to describe printing an array as O(n^2). Industry would just say this is O(n)."

Here is a my simple explanation for Big O

Big O(1) :- The time taken is somewhat constant example 2×2 will take the same time to execute as 1million x 1 million. Or time taken to cook a recipe for 1 person is almost the same as time taken to cook for 5 people

Big O(n) :- The time taken grows linearly as the data size goes up:- Example If there 10 people you have to cook for 1 person at a time from start to finish. so if it takes 1 hour to make 1 dish per person for 10 people it will take roughly 10 hours

BigO(n^2) :- This is a bit complicated but imagine: Example if there 2 people you have to cook 2 dishes for each (total dishes=4). If there are 3 people you have to cook 3 dishes for each(total dishes 9). if there are 4 people you have to cook 4 dishes for each person(total dishes 16). If there are 5 people you have to cook 5 dishes for each person(total dishes 25). So if you notice the time taken is (n^2) Number of people (times) Number of dishes.

BigO(n^3) :- Now look at this algorithm, Imagine there are 2 people For every person you have to make the same number of dishes like the previous example. Now add Alcoholic beverages to the mix, so if there are 2 people 2 drinks per dish. So if there are 3 people you will make 3 drinks per dish. 4 people 4 drinks per dish. If there are 5 people you will make 5 drinks per dish. Now calculate the total number of drinks for 2 people.

Total Drinks = 2 people * 2 dishes per/person * 2 drinks per dish = 2*2*2 = 2^3

Total Drinks = 3 people*3 dishes per/person*3 drinks per dish = 3*3*3 = 3^3

Total Drinks = n people *n dishes/person*n drinks per dish = n*n*n = n^3

so the time taken for just the drinks, will be a cube of n( where n is number of people)

That sure is one fast pigeon, flying 50 miles an hour!

A simple thank you!

And when is log n used?

Why did you say that there are n^2 pairs? Arent there like (n-1)n/2 pairs? or n choose 2 pairs? Does that matter or did you just simplify beyond the largest term n^2 in its simplification?

nice refresher, thanks

Irritating accent😑

The last example shows an algorithm O(a*b) not O(N2)

Pigeon is very naughty.

ok but how fast would the data transfer be if they used an African or European swallow??

Marry me Gayle ?

Why do you not speak clearly?

man her voice is annoying

Gayle – I'm curious what tool you used for drawing the various slides. Looks like it might be a freehand drawing tool and looks great.

Mowing a lawn is O(n).

Thanks a lot!

Where can I find a decent O(log N) example? I

Great story!

As i read in a book "Cracking the coding interview" , there are five things you have to do or need to have to join good tech companies , there are : 1 – Analytical skills 2- Coding skills 3- Computer science fundamentals 4- experience 5- communications skills ) , but do not know how to get them or what should i do to have these things ?

BIG O! ITS SHOW TIME!!!

Spit the marbles out before speaking, lady.

Kya bolna cha rahi he😂😂

What did happen with this on HackerRank?

gross its a woman

Didn't know Charlize Theron was a programmer.

i need this type of teaching. Fun, understandable and useful.

Book on Russian “карьера программиста» on each video)

I'm giving up software for carrier pigeons.

But if I have O(n*log(n)) then I'm not allowed to drop the log(n) even though n would be dominant over log(n), right? Why is that?

Wait, what about Olog(n). Pretty important to note.

Very well

Best

Amazing explanation!! Please post more videos..

Thank you for the video. Why would pigeon transferring data be constant time? I thought a pigeon would certainly have a limitation on how fast it can deliver the data according to the size of the data.

I don't understand why O notation is the worst case. If this notations describes a function f such that 0 <= f <= cg, we can see that in any case f will be smaller that the original function g that describes the running time. In my idea, f describes a better option because the running time is less for any input n. Someone can explain me please why O notation is the worst case?

Why is there a Korean coding book in the background lol

Amazing video!

i loved that bird 😀

Big egO Notation.

didn't click 🙁

Even though I've had to survive from programming for all sorts of clients for almost 15 years, I now find myself having to learn these things if I want to settle down, get a job with a six figure salary. Truly nothing wrong with this, even though I've been told that I'm not a senior programmer. Which is correct, but I'm a senior in relationship development, sales, customer support, tolerance, fixing programming issues, doing whatever it takes to get the job done, and building real world applications. It's hard to tell an interviewer that has no real world experience these things without telling them to F off.

I've disregarded my big Ego, and have been studying these things, taking online courses for Golang, and I now feel more confident that I can compete with my vocabulary and understanding of the computer science mumbo jumbo. It's truly an exciting step because after you learn just the bits and pieces, you indeed put yourself in a position to earn a wonderful living as a programmer.

Wish you all the best of luck on your endeavors.

if the example at 4:55 is O(a+b) then why is the example (the top one) starting at 5:26 O(n)? Running thru the array for finding Min value first can be looked at as doStep01() and then running thru the array for finding Max value can be looked at as doStep02() thus becoming O(a+b) here as well. How did that become O(n) ?

you are pregnant

This is killing me right now in CS…

I dropped out of school due to illness and did a test to get into uni years later.

I know I can code and test the efficiency of my programs using these theories in practice.

But if it ever gets asked of me in a interview to explain the proper math terms and lingo I'm screwed.

I'll get it now but in the future I won't remember this stuff, I'll only remember the practice I've had with actual algorithm implementation and refactoring.

props to the bumpy pigeon animation. I had a good chuckle. Also very good explanation

ok, I'm a college student, and i must say this is the worst explanation video that you could find on the internet, just saying a couple of stupid rules out of nowhere. I was expecting a better mathematical explanation of the notation and it's usage than in my subject script. this is just stupid. Also the animations are terrible, more distracting rather then helpful. Especially this part 6:25. "N must have a meaning", well WTF is the meaning. That's what you should explain in your video instead, the logical why behind all this. Not act as a smartass lady that knows all better.

Why is a woman narrating this video?

Excellent !!!

Pause @0:03 topkek!!

So what did you have in breakfast?

Electrons!

In the 4th drop non dominate terms here a nd b are 2 variabales since we don't know a=b how n^2 ? Rather it should be a*b

Very Good. Thanks from Brazil!

I have been a software developer for almost 40 years. I have NO CLUE what she's talking about. Actually, I do but never in those terms. Seems that something fairly basic has been mystified so as to trip up people during interviews.

I got my finals in 3 weeks and I'm 90% sure they're going to ask this in relation to Lists and Sets 😭

Big O notation seems like so much hand waving to me …

BIG O is dropping a new song soon.

I studied this in my CS course 15 years back. After that I never got a chance to use it in practice.

No discussion of P = NP?

3:20 Always good to see someone who knows how to draw a square…

Thanks a lot, very informative 🙂

thank you for the clear explanation

Is big O different in pure mathematics?

slaps lipsI thought the big “O” was when your wife or girlfriend stopped complaining.

love this woman

That's why I used hashmap now instead of nested loops

PTP – Pigeon Transfer Protocol

Aaand… what is O(log n)

barack uhhhhhhhhhhh obama

thanks a lot!

I was literally zooming those books behind her for a moment.

Great explanation of Big O but for the love of god please use a readable font for those coding snippets.

This explanation is freaking awesome

good that she wrote the book because her voice is sometime annoying

could use a proper font for your code. it's difficult to read code in that font