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
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.
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.
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 :-)
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)
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.
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.
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!
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.
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?
“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.
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) ?
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) ?
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.
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.
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..
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
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.
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)
This might be a stupid question, however i'm completely new to CompSci; at 06:50, the big O of the function that for each element in a runs through b to check for pairs, is O(axb). At 07:13, a similar function appears but this time has big O(n^2) - why is that not O(axb)?
the former function consists of 2 different arrays that may not be of the same sizes...hence need to consider both of their sizes individually.. but the latter includes a single array, which means n x n = n^2
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?
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.
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.
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)
I'm confused: If I iterate an array and also again per each item being read in the array I read again all the array, shouldn't it be O(a + a*b) or O(n + nn) ? (sorry I used nn instead of n square)
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
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
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)."
Vineet Chaudhary Other than Big O, there’s also Big Omega and Big Theta. Big O provides an upper boundary, while Big Omega provides a lower boundary. Big Theta provides both lower and upper boundaries. Eg. An algorithm with the time complexity of n^2 + 2 is Big O(n^2), but technically it is not incorrect when written as Big O(n^3) or even Big O(n^4). On the other hand, n^2 + 2 is Big Omega(n^2). It is also not incorrect when written as Big Omega(n) or even Big Omega(1). However, n^2 + 2 can only be Big Theta(n^2), because it is lower and upper bounded by n^2. Basically in the industry when they ask for Big O, they are actually asking for Big Theta.
Kind of like when someone ask you if how long does it take to walk to the nearest supermarket that’s 5 minutes away. You can say “Under 12 hours” which is technically correct. However it would be much more accurate to say “Under 10 minutes”.
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?
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.
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.
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
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
Thanks so much, this 8 minute video made it way more clear than several hours of lectures and readings
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
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.
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.
HackerRank: Hi, Im Gayle Laakmann McDowell, author of Cracking the Coding Interview.
me: i am aware
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 :-)
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?
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.
The best video after spending hours I finally understood the big O!Thanks
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.
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.
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!
We need some O(log n) and O(n log n).
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.
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)
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)
7:13 function whyWhouldIDoThis(array) {return lol;}
Error: unused variable. 'array' is not used
@@CJRH1FILMS thats a warning not an error :p
The pigeon/Internet anecdote bears a striking resemblance the plot of Terry Pratchett's 'Going postal'
“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.
that introduction really helped put this subject into perspective
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?
Thank You for this video. I reached here after checking many other links .This is the best .
Thanks for giving an explanation that someone without much knowledge of maths understands by giving practical examples :-)
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.
3:20 Always good to see someone who knows how to draw a square...
it is a square, just not drawn to scale.
perspective
Love your Graphics and Colors that are used for the Demonstration . makes it interesting to watch .
i agree!!!!!!!!
@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.
@@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?
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)
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.
i love this woman, she helped me so much
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
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!
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.
HOLY SHIT, THANK YOU SO MUCH. So wish you were my lecturer cause this made so much more sense than anything he ever said!
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'm from SA. I remember this 'exercise'. My brother even did a cartoon about it :-)
Anyway, good explanation. Thanks.
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.
I've studied many ressources on that subject, but it's finally on yours that I got the concept. Cheeeeeeeeeeeeers!!
Such a revolutionary explanation of Big O.
I appreciate the bird moving at the end. Fun touch.
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
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
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 studied this in my CS course 15 years back. After that I never got a chance to use it in practice.
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.
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)
fav video for the concept..
gonna recommend to all my juniors.
Wow, Thank you sooo much!
This video helped me a lot for studying for my finals.
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.
So, did Hitchcock make a DDOS attack in "The Birds"?
haha
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.
You had to be an amazing note taker in school. Thanks for the explanation
This is a wonderfully clear explanation.
This is the clearest intro on Big O
Why Hackerrank is not organising contests anymore 🙄?
Nice point to highlight at 6:23 .. it's small but I caught out doing this in an interview before.
How did printing pairs became O of N2?
This might be a stupid question, however i'm completely new to CompSci; at 06:50, the big O of the function that for each element in a runs through b to check for pairs, is O(axb). At 07:13, a similar function appears but this time has big O(n^2) - why is that not O(axb)?
the former function consists of 2 different arrays that may not be of the same sizes...hence need to consider both of their sizes individually..
but the latter includes a single array, which means n x n = n^2
i need this type of teaching. Fun, understandable and useful.
I really love this video, they really did a great job here.
What the heck. I was reading her book and I went to RUclips 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
"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"
Excellent explanation! Thanks for simplifying Big O concepts.
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?
Does the square plot look like a rectangle only to me?
that pigeon analogy finally made it click for me.
Straightforward. Easy to understand. Cool graphics! Hats off =)
If you were to have three for each loops would that be O(n^3) instead of O(n^2)?
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.
Thank you very much, better than my CS PhD. Professors.
So it's about how many times the function scales, and not how much time it takes to run
This is what I needed to level up thank you soo much.
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.
Very well explained mam
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?
I'm confused: If I iterate an array and also again per each item being read in the array I read again all the array, shouldn't it be O(a + a*b) or O(n + nn) ? (sorry I used nn instead of n square)
I like how the pigeon flies over to the g at 2:26
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
so this vid was for time complexity not space complexity?
thank you! It really cleares stuff up :D
That's why I used hashmap now instead of nested loops
Well explained about representing O as a function of N under different scenarios.
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...
4:16 it's interesting that she uses meter as the length unit given that she's American
mathematical professionals use the si units
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)."
Vineet Chaudhary
Other than Big O, there’s also Big Omega and Big Theta.
Big O provides an upper boundary, while Big Omega provides a lower boundary. Big Theta provides both lower and upper boundaries.
Eg. An algorithm with the time complexity of n^2 + 2 is Big O(n^2), but technically it is not incorrect when written as Big O(n^3) or even Big O(n^4).
On the other hand, n^2 + 2 is Big Omega(n^2). It is also not incorrect when written as Big Omega(n) or even Big Omega(1).
However, n^2 + 2 can only be Big Theta(n^2), because it is lower and upper bounded by n^2.
Basically in the industry when they ask for Big O, they are actually asking for Big Theta.
Kind of like when someone ask you if how long does it take to walk to the nearest supermarket that’s 5 minutes away.
You can say “Under 12 hours” which is technically correct. However it would be much more accurate to say “Under 10 minutes”.
Thanks , the concepts are now clear , time to solve questions
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
A very concise and to-the-point video. Thanks!
Finally a good explanation! Couldn't understand it with my lazy ass teacher... Thank you!
ok but how fast would the data transfer be if they used an African or European swallow??
Great video, good theme the big O notation is very interesting