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).
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)
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.
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.
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).
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.
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.
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.
@@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?
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
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.
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.
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*
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 :-)
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.
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.
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)
“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.
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?
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!
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)
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.
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.
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
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?
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?
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)
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)
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!
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.
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.
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
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..
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?
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.
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) ?
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
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.
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) ?
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?
For those who didn't get it the first time (It took me way longer than it should have to understand what exactly big O notation actually does), here's a simple explanation. Basically what Big O does is show you how many times it TOOK to RUN a certain section to get a certain result.
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
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).
Chris Hill, good analogy. For O(log n) one dish is being served to all the groups or a dish for each group?
One dish per group.
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)
This analogy is fire!!!
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.
So Big O is not a rapper?
That's Big L
Good one. Is the world ready ? What do we call it. Dat-rap? Chip-hop?
That's Lil O
haha
You're thinking of The Notorious BIG O.
PTP - Pigeon Transfer Protocol
LOL
YES!
ah yes
I’d buy it😆
But did they account for the time to transfer the data on and off the drive?
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.
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).
You probably are
sometimes it feels frustrating that the interviewer knowledge is limited and he is just denying the same fact.
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.
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.
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.
How you doin' mate
@@PauloHenrique-pk5ro Absolutely phenomenal. 2022 brought along with it some new experiences and opportunities. And yourself?
@@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!
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
Clicked this because it was 8 mins, straight to the point, no unnecessary knowledge. Loved it
Yeah, I just hate to watch those one hour long explanations.
oh my god for the first few minutes I thought it is an ad.
lol me too
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.
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.
Nah
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
He's d greatest
true that
Thanks so much, this 8 minute video made it way more clear than several hours of lectures and readings
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*
**fake laugh**
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 :-)
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.
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.
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)
For 4.40 : Cpu follow the steps one by one so you add them up.
“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?
O(sx)
the chances are O(NO)
Chances = Big O / 0
chances - Big NO
Binary search on an ordered array?
that introduction really helped put this subject into perspective
HackerRank: Hi, Im Gayle Laakmann McDowell, author of Cracking the Coding Interview.
me: i am aware
The best video after spending hours I finally understood the big O!Thanks
Wtf.....watched so many videos to understand this concept....and here u are explaining the same topic in an easy way...❤️❤️
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?
Because it is same array it has same inputs so o(n*2)
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!
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)
Samir Tendulkar Log explain?
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.
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.
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.
The pigeon/Internet anecdote bears a striking resemblance the plot of Terry Pratchett's 'Going postal'
We need some O(log n) and O(n log n).
I'm from SA. I remember this 'exercise'. My brother even did a cartoon about it :-)
Anyway, good explanation. Thanks.
Thanks for giving an explanation that someone without much knowledge of maths understands by giving practical examples :-)
Love your Graphics and Colors that are used for the Demonstration . makes it interesting to watch .
i agree!!!!!!!!
HOLY SHIT, THANK YOU SO MUCH. So wish you were my lecturer cause this made so much more sense than anything he ever said!
Thank You for this video. I reached here after checking many other links .This is the best .
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***
How d'you find out? What d'you encounter?
I appreciate the bird moving at the end. Fun touch.
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)
i love this woman, she helped me so much
Such a revolutionary explanation of Big O.
I think it makes more sense to say you drop coefficients - not constants.
lol truuu
Chris A. Both get dropped
Both of them get dropped.
Both of those two things -- one, and also the other -- they both get dropped.
n^2 = n * n, no constants|coefficients there
"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"
I've studied many ressources on that subject, but it's finally on yours that I got the concept. Cheeeeeeeeeeeeers!!
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...
it is a square, just not drawn to scale.
perspective
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
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.
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.
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?
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
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?
Answer to this ?!
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)
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)
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!
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.
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.
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.
i need this type of teaching. Fun, understandable and useful.
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 the clearest intro on Big O
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.
fav video for the concept..
gonna recommend to all my juniors.
You had to be an amazing note taker in school. Thanks for the explanation
7:13 function whyWhouldIDoThis(array) {return lol;}
Error: unused variable. 'array' is not used
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..
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
Thanks mustafa!! :)
Don't worry she didn't explain it very well.
Thanks for the EDIT , because i was thinking the same :)) .
Ah, this confused me too
Wow, Thank you sooo much!
This video helped me a lot for studying for my finals.
This is a wonderfully clear explanation.
So, did Hitchcock make a DDOS attack in "The Birds"?
haha
Finally a good explanation! Couldn't understand it with my lazy ass teacher... Thank you!
What the heck. I was reading her book and I went to UA-cam to reinforce the concepts and this was the first video I picked.
Same. GAYLE ARE YOU WATCHING ME ;A;
Do you recommend the book?
Sane here 😄
this event occured to me now
Excellent explanation! Thanks for simplifying Big O concepts.
that pigeon analogy finally made it click for me.
I really love this video, they really did a great job here.
thank you! It really cleares stuff up :D
This is what I needed to level up thank you soo much.
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?
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.
Straightforward. Easy to understand. Cool graphics! Hats off =)
The easiest explanation about Big O in the internet so far.
Thank you and it is really helpful.
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) ?
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)
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
Thank you very much, better than my CS PhD. Professors.
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.
A very concise and to-the-point video. Thanks!
Very well explained mam
Thats a great explanation , supercrisp and helpful for interviews .
Finally I understood Big O - Thanks a ton !!
Cast in the name of god, ye not guilty...
Big O, Action!
BIG O SHOWTIME!!!!!!!!!!!!!!!!
props to the bumpy pigeon animation. I had a good chuckle. Also very good explanation
So it's about how many times the function scales, and not how much time it takes to run
I loved the story as well as the explanation. I also knew the pigeon is going to win:-)
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) ?
I thought the same as you buddy.
Very nice video!
It has a faster airspeed velocity because it's an African Pigeon.
Holy grail reference?
This is borderline racist
Great video, good theme the big O notation is very interesting
Thanks , the concepts are now clear , time to solve questions
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?
For those who didn't get it the first time (It took me way longer than it should have to understand what exactly big O notation actually does), here's a simple explanation. Basically what Big O does is show you how many times it TOOK to RUN a certain section to get a certain result.
Nice point to highlight at 6:23 .. it's small but I caught out doing this in an interview before.
I don't understand why O notation is the worst case. If this notations describes a function f such that 0
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
Not to mention if it's also carrying a coconut...
Why Hackerrank is not organising contests anymore 🙄?
i loved the example
That's why I used hashmap now instead of nested loops
Really creative explanation for solidifying our basics. :)
Well explained about representing O as a function of N under different scenarios.
I think i can still argue though that the pigeon may just take longer due to the weight of the USB stick back in the days lmao :P