Big O Notation 

So Big O is not a rapper?

Here's my favorite Big O analogy: Let's say you're making dinner for your family. O is the process of following a recipe, and n is the number of times you follow a recipe. O - you make one dish that everyone eats whether they like it or not. You follow one recipe from top to bottom, then serve (1 recipe).

PTP - Pigeon Transfer Protocol

I might be too stupid to be a software developer. Unfortunately, I have learned this after 20 years of being a software developer. There are some things you need to know to impress people interviewing you that you may never touch on the job.

oh my god for the first few minutes I thought it is an ad.

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

Gayle!!! I just started reading cracking the coding interview and what a pleasant surprise to stumble upon this channel. Great educator and author. Thanks for the video :-)

What a simple but clear explanation on Big O. I finally found you. Many videos start off with even more complex mathematical terms that are difficult to understand by themselves. You start very simply. Magnificent! How about one on Tractability to help.

Clicked this because it was 8 mins, straight to the point, no unnecessary knowledge. Loved it

Although you left some other necessary o notations, your lectures are great! I'm glad i found your lectures, straight to the point and an understandable dialect.

Good video. People say McDowell's lessons aren't important and are never used outside of interviews, but big O notation is actually important. I learned this the first time I used nested for loops.

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

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.

that introduction really helped put this subject into perspective

Thanks for giving an explanation that someone without much knowledge of maths understands by giving practical examples :-)

Excellent explanation! Thanks for simplifying Big O concepts.

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

HOLY SHIT, THANK YOU SO MUCH. So wish you were my lecturer cause this made so much more sense than anything he ever said!

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

The pigeon/Internet anecdote bears a striking resemblance the plot of Terry Pratchett's 'Going postal'

Such a revolutionary explanation of Big O.

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.

I've studied many ressources on that subject, but it's finally on yours that I got the concept. Cheeeeeeeeeeeeers!!

The best video after spending hours I finally understood the big O!Thanks

Such a great explanation. I can flip a string with xor but I couldn't get Big O for the life of me. The meaningless N got me so confused before. Thank You!

HackerRank: Hi, Im Gayle Laakmann McDowell, author of Cracking the Coding Interview. me: i am aware

Really creative explanation for solidifying our basics. :)

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.

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

Me: Man, I'm so confused by this class. What the heck is Big O? Gayle: Let's talk about one of my FAVOURITE things! Me: *feels even worse about struggling*

Wtf.....watched so many videos to understand this concept....and here u are explaining the same topic in an easy way...❤️❤️

I'm from SA. I remember this 'exercise'. My brother even did a cartoon about it :-) Anyway, good explanation. Thanks.

Thank You for this video. I reached here after checking many other links .This is the best .

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

This is a wonderfully clear explanation.

I enjoyed this. As a person who didn't have a background in Math or CS, this was very understandable. Now, I just need to remember and practice.

I really love this video, they really did a great job here.

We need some O(log n) and O(n log n).

Thank you sooo much for this...so to the point and simplified

Love your video! very clear and concise

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

You had to be an amazing note taker in school. Thanks for the explanation

Thats a great explanation , supercrisp and helpful for interviews .

i love this woman, she helped me so much

I have seen this and read Cracking the Coding Interview 6 and this explanation is far far far superior, but the book explains O(log N) and more complex algorithms

This is what I needed to level up thank you soo much.

best lecture i have seen so far

Well explained about representing O as a function of N under different scenarios.

1:35 Describing the pigeon transfer speed in Big O notation 2:00 What Big O is as an equation - scales linearly with respect to the amount of input 2:10 Summary of Big O 4:35 4 important rules for Big O Notation 4:40 Why Big O is related to factorial (I think)

Amazing explanation!! Please post more videos..

Thanks , the concepts are now clear , time to solve questions

Love your Graphics and Colors that are used for the Demonstration . makes it interesting to watch .

Finally I understood Big O - Thanks a ton !!

fav video for the concept.. gonna recommend to all my juniors.

Great explanation! Easy way to get it.

“DON’T BE LAZY!!!” is right. I was lazy for my Google interview because of the low stakes (I already have a job I am happy with) and fumbled almost every BigO question. It came up in every round. I knew which was faster intuitively, but found it hard to represent the correct notation. Learn this as it is very very important to fully grasp it. Also, know the BigO notations for most of the built in functions for your chosen language.

Very strong overall explanation. What are the chances of getting a video showing some real world giveaways for more complex Os, like O(log N) etc?

Its a really helpful video, made the concept pretty clear the only one thing is that it would have been better if an example of O(log(n)) would have also been there

I appreciate the bird moving at the end. Fun touch.

Very Good. Thanks from Brazil!

Great video, good theme the big O notation is very interesting

Great explanation, thank you

Great explanation, thanks!

Once, I used to thought that algorithm efficiency is not going to be a problem for me. ***believe me, I learned the lesson, hard way***

thank you for the clear explanation

Great colors!😊

Nice point to highlight at 6:23 .. it's small but I caught out doing this in an interview before.

amazing explanation. thank you

Very good explanation. Subbed!

Well explained, thanks :)

Best explanation I've seen

This is the clearest intro on Big O

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

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

Really good explanation!

Thank you for such a good, short, and comprehensive explanation of the big-O notation. It was really helpful. I just wanted to clarify my understanding: according to rule 3 (different inputs => different variables), in the rule 4 explanation, there should be O(a + a*b) => O(a*b) instead of O(n + n^2) => O(n^2), shouldn't it?

Thank you, it was really helpful.

Great explanation!

Finally a good explanation! Couldn't understand it with my lazy ass teacher... Thank you!

Big O explained using a pigeon! What the heck! It’s so simple yet so effective that I want to cry. Thank you, Gayle! You are a gift to all programmers!

I liked last four points to calculate asymptotic notation value.

I loved the story as well as the explanation. I also knew the pigeon is going to win:-)

nice refresher, thanks

Thanks so much, its life-saving

you use non dominant dropping when you take the run time of the nested for loop itself right?, it should be a*b + a and you drop the non dominant 'a' to get O(a*b). You should explain that earlier, but fantastic video

If I understand this right, we should run benchmarks when nesting loops inside of loops (add more data to our tests and see if the increase is exponentially rising). It's really easy to exponentially slow down processes, and there's usually a clever, more performant, path.

thank you! It really cleares stuff up :D

I've noticed the books in the background were written each one in the different language, so I can suppose you read/listen/speak two or three idioms besides the English, right?

Very good, thanks. Please note that sometimes people pronounce O(1) as "order 1", O(n) as "order n", O(n^2) as "order n squared", etc.

Just Great Explanation..

Thank you and it is really helpful.

Thanks for clear explanation ..

Very comfortable to understand. One thing i considered that: why we removed the instants -> O(50n) = O(n) ? Admit that the results wont depend much on instants but how ab the instant with >1000 ? It's matter.

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

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

7:13 function whyWhouldIDoThis(array) {return lol;}

Very nice video!

I think it makes more sense to say you drop coefficients - not constants.

nice examples thank you

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.