Big O Notation

[@codinginflow]

So Big O is not a rapper?

[@allenllewellynkra]

That's Big L

[@陈瀚龙]

Good one. Is the world ready ? What do we call it. Dat-rap? Chip-hop?

[@rbp365]

That's Lil O

[@ChildishJordino]

haha

[@mainpost4111]

You're thinking of The Notorious BIG O.

[@christinehill4584]

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

[@shubhamnegi1937]

Chris Hill, good analogy. For O(log n) one dish is being served to all the groups or a dish for each group?

[@B-Billy]

One dish per group.

[@me-zz2340]

O(n^2) analogy is not very good. I think if every person in your family makes individual dish for every person (so every person will have n dishes) - this could be O(n^2)

[@spray-r9951]

This analogy is fire!!!

[@flybeep1661]

Simon WoodburyForget I guess you don't know what an "analogy" is. You just explained it in your way without making an analogy at all. Using analogies is a way to describe complex concepts in an as simple as possible way. The simpler the explanation the better the analogy. You just explained it in a fashion you would understand it best which isn't necessary the best way for others. Making anlalogies circumvents this problem. I hope you're not a teacher, you wouldn't be good at it.

[@joe44850]

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.

[@fierce10]

An older interviewer who was a director at a company failed me because he asked a question on this and he didn't know to drop coefficients. He insisted in the interview that its O(2N) and I got it wrong by saying its O(N).

[@spray-r9951]

You probably are

[@rxtx3948]

sometimes it feels frustrating that the interviewer knowledge is limited and he is just denying the same fact.

[@danbo967]

My take on all this is this, if you work for a company that processes few records (entities, etc.) you usually are fine without complex algorithms unless you have to do complex operations. If the company processes a lot of records it becomes increasingly helpful (O(N)... did you get it ) to use algorithms and Big-O notation. Especially for companies that are algorithm intensive like Amazon, Facebook, Google, etc.

[@funinchico84]

No. It allows you to *prove* that an alternative is more/less efficient. If a developer can only come up with O(n^2) solution, then big O can tell you it's slow. Which is exactly what my computer can tell me with benchmarks. There's a benefit to knowing the notation, but it doesn't automatically make your code more efficient.

[@lassulfi]

PTP - Pigeon Transfer Protocol

[@akoshileolalekan5364]

LOL

[@FluffyNinjaUnicorn3Gaming]

YES!

[@dakshdangwal]

ah yes

[@seńor_t007]

I’d buy it😆

[@mrkinetic]

But did they account for the time to transfer the data on and off the drive?

[@user-gp8fr1nd3w]

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

[@CodeWithYubraj]

lol me too

[@swissmatteo]

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.

[@PauloHenrique-pk5ro]

How you doin' mate

[@swissmatteo]

​@@PauloHenrique-pk5ro Absolutely phenomenal. 2022 brought along with it some new experiences and opportunities. And yourself?

[@PauloHenrique-pk5ro]

@@swissmatteo I feel happy for you! I'm just an 18yo Beginner studying Basis Concepts to start Programming... Also trying my way to college, I'm nobody, yet. 😅 Care to share your GitHub Profile?

[@สุภาพรสามงามเอี่ยม]

Absolutely mate i hope you're doing well!

[@user-xx7tv7cc1y]

I sympathise with you man, i joined a grad scheme years ago and all of the people i joined with all went our seperate ways and they made it through the ranks from fixing things here and there, doing some simple apps reading from a database and returning via an API. I did the same, but i always made sure to write as much code as I could. I even did coding tests online just to keep my skills sharp and do personal projects, even if they were small. eventually im able to get a 6 figure job because ive got real world experience but i also can program. all my friends who did less and less code as they went up realised that they were just working in average companies and just became knowledable about the systems they maintained, the second they want to go into the larger companies that are doing the best work and actually got asked engineering problems, they realise they had wasted 10 or so years doing maintainece work with the simple day to day getter and setter updates

[@extremeloco23]

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

[@Ankit-zu2kp]

Yeah, I just hate to watch those one hour long explanations.

[@jameswon5497]

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

[@Afrovo]

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

[@theBIGgee]

He's d greatest

[@akashgkrishnan9596]

true that

[@yongaisim6845]

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.

[@changeorbeextinct]

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.

[@Rei-m3g]

Nah

[@Michael-AC]

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*

[@michaeljeffrey5382]

**fake laugh**

[@latedeveloper7836]

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)

[@howdoyouturnthison7827]

For 4.40 : Cpu follow the steps one by one so you add them up.

[@vincentbuscarello1357]

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?

[@Jerkwaad]

O(sx)

[@evantheking]

the chances are O(NO)

[@igrewold]

Chances = Big O / 0

[@bik8353]

chances - Big NO

[@hellolin324]

Binary search on an ordered array?

[@JonathanMontgomery77]

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

[@shehrozeshahzad581]

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

[@volo7]

that introduction really helped put this subject into perspective

[@sindhusasidharan6762]

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

[@connergesbocker9902]

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

[@10uRization]

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.

[@daramolapraise]

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

[@jordi5316]

i love this woman, she helped me so much

[@mobileappmike]

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.

[@MrMukulpandey]

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

[@rodrigosodre2655]

In rule 3 you told the (for b) inside (for a) loop should not be O(n^2) but O(a x b) but the same structure in rule 4 you wrote O(n^2)

[@samnik12345]

Here is a my simple explanation for Big O Big O(1) :- The time taken is somewhat constant example 2x2 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)

[@alexwang982]

Samir Tendulkar Log explain?

[@MrMrWazzaa]

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

[@srinivasnangunuri1313]

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

[@spray-r9951]

i agree!!!!!!!!

[@Owen-]

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

[@BillionaireDeveloper]

Such a revolutionary explanation of Big O.

[@mikhailsidorov8689]

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?

[@sollork8135]

Because it is same array it has same inputs so o(n*2)

[@CaseyMartin]

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

[@kaieden]

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

[@himanshuk2873]

"Hi, I'm Gayle Laakmann McDowell, author of Cracking the Coding Interview" "hi I'm gay lock MacDowell author of crack including interview" "hi I'm Dale lock McDowell author of Krakens pudding interview" "hi I'm Gail laughs McDowell author of Kraft encoding interview" "hi I'm Cale lack McDowell off of cracks and footing interview" "hi I'm Gaelic McDowell off of Cox encoding interview" "hi I'm Gail wok McDowell autocrats encoding the interview" "hi I'm Kayla Loch McDowell author of crack and cutting interview" "hi I'm Gail Locke McDowell author of crack and coding interview"

[@matexxo4004]

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

[@CapnAhabChannel]

At 6:25 you say the nested loops are NOT N^2 but a*b. Yet at 7:24 you call the same nested loops n^2 and NOT a*b. Surely, both can't be right!? Have I missed something?

[@nozzlium]

In the first example the code iterates 2 different arrays (a iterates arrayA, b iterates arrayB) that’s why they are represented by two different variables, while in the second exampe both a and b iterates the same array.

[@thinhle1339]

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.

[@crewlylehintal9451]

That's because you haven't studied Big O notation in depth. This video doesn't explain what Big O actually is or where it comes from. Big O notation is defined in terms of set theory. O of a function let's say g(n), O(g(n)), is defined as the set of all functions f(n) such that there exists constants c and n0, where cg(n) is greater than or equal to f(n) for some n > n0. Big O is not necessarily defined for algorithms, it's defined for all functions as an asymptotic notation. Edit: I suggest you study other asymptotic notations as well such as big Omega notation, theta notation, small o notation and small omega notation.

[@jyrikgauldurson8169]

That doesn't explain anything, that's just the formal definition in text which is better read in real notation. Also, sometimes constants do matter.

[@JagjotSingh]

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

[@TheN0odles]

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

[@nistr2]

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

[@mustafas126]

lol truuu

[@espressothoughts]

Chris A. Both get dropped

[@JoseAguirre-ri8tg]

Both of them get dropped.

[@lancetschirhart7676]

Both of those two things -- one, and also the other -- they both get dropped.

[@wolfboyft]

n^2 = n * n, no constants|coefficients there

[@mayank_upadhyay_19]

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***

[@hopeklein6537]

How d'you find out? What d'you encounter?

[@Wiejeben]

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

[@scottishfoldmocha5875]

The first rule contradicts the second one -if I have 2 loops 'a' and 'b' you are saying I need to add times -'a' +'b' , but then how come if I need to run SAME loop two times it is not 'a'+'a' but only 'a'??? I think first rule should be to take the longer loop: max(a,b). Your #1 rule is also contradicts to your #4 - dropping non-dominant terms.

[@subhamengine1143]

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

[@soham7226]

Why Hackerrank is not organising contests anymore 🙄?

[@johannsebastianbach3411]

So, did Hitchcock make a DDOS attack in "The Birds"?

[@lokeshwartailor8250]

haha

[@farisalsaad]

Question: You said in step 3 not to use n^2 for the two for loops that output the elements of the arrays (1,2). But in step 4 you use n^2 to describe the two for loops for the elements of the arrays (1,2). Why is that?

[@qu4tschk0pf]

Faris Alsaad because in the first example they were executed one after the other and in the second example the first loop contained the second loop

[@egan108]

in the first example, the loop is contained in the second. its the exact same scenario yet she used n^2 instead of saying a*b and i dont get why. can anyone explain why?

[@santiagom7]

Answer to this ?!

[@mahwishj.6859]

in example 3, you're checking each element in arrayA and then each element in arrayB. arrayA and arrayB may be of different sizes, therefore you can't assume that they're of the same size. so you do O(a*b). in example 4, you're looking for each a and for each b in the *same array*. that means that you're iterating through the same array and so it'll be the same size. so you do O(n^2)

[@giannagrace6315]

I noticed this and it confused me too, but after looking at both codes again I think that in step 3's code, there are two arrays: the first loop goes through the first array and the nested loop goes through the second array, counting how many elements arrayA and arrayB share, the lengths of both arrays are independent of each other (if a changes, b doesn't necessarily have to change). In step 4's code, there is only one array, and the nested for loop just ends up printing the different coordinate pairs of the array, there is only one array length, a and b are dependent on each other (if a changes, b changes)

[@msesbreno]

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!

[@awaisn]

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

[@chris9300]

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.

[@ultimatesin3544]

6:20 - you say it's NOT O(n^2)... 7:24 - you say it is.. I don't understand why in the first example you say it's not.. both of them are O(n^2) correct?? EDIT - oh nevermind I'm an idiot.. it's because in first example both arrays may be of different length, in second example it's the same array so same length..

[@mustafas126]

6:20 is 2 arrays possibly diff size looped through so a*b and 7:24 is the same size array looped so n*n or n^2

[@Chiving]

Thanks mustafa!! :)

[@boyracer3000]

Don't worry she didn't explain it very well.

[@alexandruberende6682]

Thanks for the EDIT , because i was thinking the same :)) .

[@liamlindsay6082]

Ah, this confused me too

[@stephenday4834]

This is a wonderfully clear explanation.

[@marie2136]

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

[@Lokaine01]

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

[@thekrisho]

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

[@CJRH1FILMS]

Error: unused variable. 'array' is not used

[@stefkodak]

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

[@francisaiello6197]

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.

[@CoryTheSimmons]

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.

[@tear728]

An easier way to do it is to find the complexity of the algorithm mathematically and then from there on you know exactly what you're dealing with.

[@LBC_squared]

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!

[@music-jj2pl]

So we use meaningful variables in the Big O notation not always n - cool. Next example @7:35 has a and b variable with no n variable and the answer is ... Big O (n^2)! Shouldn't it be Big O (a*b) ?

[@victormoura7276]

I thought the same as you buddy.

[@GlynNormington]

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.

[@billbottletop5140]

that pigeon analogy finally made it click for me.

[@inframatic]

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

[@samr6781]

Does the square plot look like a rectangle only to me?

[@momentouscrazynoob1709]

thank you! It really cleares stuff up :D

[@tekamanurag6065]

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

[@ButerWarrior44]

so this vid was for time complexity not space complexity?

[@allanhenriques2694]

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

[@princeOalgeria]

So it's about how many times the function scales, and not how much time it takes to run

[@MPKDilshan]

Thank you and it is really helpful.

[@vishalsoni6409]

Excellent explanation! Thanks for simplifying Big O concepts.

[@davidkumarr]

why at 6:53, the complexity is O(a*b) not O(a+b)? based on 1. different steps get added wont this just be adding?

[@Fan-fb4tz]

This is the clearest intro on Big O

[@amirmustafa622]

Very well explained mam

[@krissaurixsent7988]

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

[@stoopydmynd]

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

[@Raedabk-q6r]

i like the animation, how can i do something similar?

[@jessicalaursen1790]

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

[@nanophyr_4468]

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

[@RadicalCaveman]

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

[@hanats]

it is a square, just not drawn to scale.

[@FeLiNe418]

perspective

[@santoshsco]

Thats a great explanation , supercrisp and helpful for interviews .

[@AzaIndustries]

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.

[@nbl23]

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

[@alexmeyer2394]

Finding max = O(n), i.e. a = n, finding min = O(n), i.e. b = n, now combine it: O(a + b) = O(n + n) = O(2n), then drop the constant = O(n)

[@vterrans]

How did printing pairs became O of N2?

[@ll-sz9fl]

Thank you very much, better than my CS PhD. Professors.

[@jeanliu6762]

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

[@AdrianLParker]

@7:40 Why does O(n + n^2) reduce down to O(n^2)? I found the wording of rule #4 to be very confusing.

[@AdrianLParker]

@@AEROPHIL100 I know it's a bit abstract in the first place, but isn't reducing to the dominant term making the result wildly inaccurate?

[@ThiruSings]

Finally I understood Big O - Thanks a ton !!

[@rishikeshsarangi1245]

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

[@izavala]

i loved the example

[@kris4117]

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

[@ritickmadaan]

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

[@arthurmazzi841]

Very nice video!

[@jiayouchinese]

Wasn't Big O an anime about a big robot?

[@dreablin]

Good explanation. but texts are nearly unreadable because of the font :(

[@defense200x]

But that if the physical storage media is too big so the data has to be split across 2 or 3 usb sticks which the pigeon can't handle at once, so it would have to fly twice or even thrice

[@RadicalCaveman]

Not to mention if it's also carrying a coconut...

[@zato828]

What the heck. I was reading her book and I went to KZbin to reinforce the concepts and this was the first video I picked.

[@Jemmeh]

Same. GAYLE ARE YOU WATCHING ME ;A;

[@alexandergonzalez5975]

Do you recommend the book?

[@sufjanr9033]

Sane here 😄

[@kickbuttowsk2i]

this event occured to me now

[@xMercuryx56]

5:05 “walks thru da udder awway”

[@nathanaelbennett8286]

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

[@FreedomOfTħought]

Big O notation only exists to put across a formal and tangible argument in support of why one solution is more or less efficient than another. On its own, there is no benefit.