14
Aug

# 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
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.

Tags: , ,

• Coding in Flow says:

So Big O is not a rapper?

• Andrew Ritter says:

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)?

• Jessica Laursen says:

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

• Kẻ Ẩn Danh says:

• James Won says:

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

• Marie Joachimsmeier says:

Wow, Thank you sooo much!
This video helped me a lot for studying for my finals.

• Mr Anonymous says:

Isn't points 1 and 2 self contradictory?
🤔🤔🤔

• Priyanshu Gaur says:

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

• Andrew Sc says:

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

• Ibmiti Bmiti says:

thought big O was just a great time with a freind

• Rhea Rao says:

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

• Neo Mashego says:

I hear South Africa.I give a like

• TheoMC14 says:

Can i define big O as an algorithm

• Leo Haldan says:

nice examples thank you

• Jean Liu says:

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

• changeorbeextinct says:

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.

• Jonathan Harr says:

How do you practice this on your own?
Can I apply this to things I do daily?

• pillz says:

What.

• Dennis Macharia says:

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

• Gregory Pacheco says:

Excellent! Thanks

• wasting time says:

the link in the description goes to a 404 page

• Milan Joshi says:

girl!!! You are so beautiful!!

• Tiara Williams says:

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

• Vineet Kumar says:

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)."

• Samir Tendulkar says:

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)

• Sentient Meatbag says:

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

• Darsul says:

A simple thank you!

And when is log n used?

• Luke Sajer says:

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?

• Nipuna Sudharaka says:

nice refresher, thanks

• shriharsh bankapur says:

Irritating accent😑

• David Dayer says:

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

• Pakistan Ghoda says:

Pigeon is very naughty.

• Rémy Doucet says:

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

• funguy29 says:

Marry me Gayle ?

• ss says:

Why do you not speak clearly?

man her voice is annoying

• Francis Aiello says:

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.

• Jonny Wright says:

Mowing a lawn is O(n).

Thanks a lot!

• Valkon says:

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

• Brian Jester says:

Great story!

• Mohamed Mustafa says:

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 ?

• Darksepheroth says:

BIG O! ITS SHOW TIME!!!

• Nicholas Sway says:

Spit the marbles out before speaking, lady.

• let see says:

Kya bolna cha rahi he😂😂

• B. M. says:

What did happen with this on HackerRank?

• Shitsneeze turdhorse says:

gross its a woman

• Last First says:

Didn't know Charlize Theron was a programmer.

• Awais Noor says:

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

• Viacheslav Moshkin says:

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

• Cory Ziegler says:

I'm giving up software for carrier pigeons.

• Quasiker says:

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?

• Michael Blum says:

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

Very well

Best

• sai saketh says:

Amazing explanation!! Please post more videos..

• Yurie Egawa says:

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.

• Lars17S says:

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?

• watchcode says:

Why is there a Korean coding book in the background lol

• The Wall says:

Amazing video!

• maslak says:

i loved that bird 😀

• sam lebon says:

Big egO Notation.

didn't click 🙁

• Mateo Morales says:

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.

• nbl23 says:

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) ?

• jamal khan says:

you are pregnant

• Aza-Industries says:

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.

• Volvox says:

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

• Cody Sing says:

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.

• TheAlpha1550 says:

Why is a woman narrating this video?

• Meknassi Hamza says:

Excellent !!!

Pause @0:03 topkek!!

• shreyansh pandey says:

So what did you have in breakfast?
Electrons!

• Akshaya Kumar says:

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

• Gabriel Pereira Mendes says:

Very Good. Thanks from Brazil!

• Michael Pennington says:

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.

• J G says:

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

• Bulldawg says:

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

• DARTH ASH says:

BIG O is dropping a new song soon.

• Jagjot Singh says:

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

• Jim Carpenter says:

No discussion of P = NP?

• Michael Lubin says:

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

• rahul bajaj says:

Thanks a lot, very informative 🙂

• HAITHAM says:

thank you for the clear explanation

• Corner Shift says:

Is big O different in pure mathematics?

• Alex Powell says:

slaps lips

• Cary Clan says:

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

• Andy McBra says:

love this woman

• James Paz says:

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

• Luis Daniel Assulfi says:

PTP – Pigeon Transfer Protocol

• megasuperlexa2 says:

Aaand… what is O(log n)

• Tom Sims says:

barack uhhhhhhhhhhh obama

• Brand M says:

thanks a lot!

• JAY RATHOD says:

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

• Nathanael Bennett says:

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

• Ghabriel Mielli says:

This explanation is freaking awesome

• Jayesh choudhary says:

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

• J says:

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