Big O Notation
HTML-код
- Опубликовано: 26 сен 2016
- Learn about Big O notation, an equation that describes how the run time scales with respect to some input variables. This video is a part of HackerRank's Cracking The Coding Interview Tutorial with Gayle Laakmann McDowell. www.hackerrank.com/domains/tut...
Наука
![Megan Thee Stallion - Mamushi (feat. Yuki Chiba) [2024 London Performance]](http://i.ytimg.com/vi/pxTCJUuorKc/mqdefault.jpg)
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.
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.
oh my god for the first few minutes I thought it is an ad.
lol me too
Thanks so much, this 8 minute video made it way more clear than several hours of lectures and readings
Gayle!!! I just started reading cracking the coding interview and what a pleasant surprise to stumble upon this channel. Great educator and author. Thanks for the video :-)
What a simple but clear explanation on Big O. I finally found you. Many videos start off with even more complex mathematical terms that are difficult to understand by themselves. You start very simply. Magnificent! How about one on Tractability to help.
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.
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.
Good video. People say McDowell's lessons aren't important and are never used outside of interviews, but big O notation is actually important. I learned this the first time I used nested for loops.
This makes me realize Colt Steele's a legend. I came here after watching his tuts on big O and I was surprised at how much I already knew
He's d greatest
true that
Thanks for giving an explanation that someone without much knowledge of maths understands by giving practical examples :-)
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
that introduction really helped put this subject into perspective
Wow, Thank you sooo much!
This video helped me a lot for studying for my finals.
Excellent explanation! Thanks for simplifying Big O concepts.
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
HOLY SHIT, THANK YOU SO MUCH. So wish you were my lecturer cause this made so much more sense than anything he ever said!
A very concise and to-the-point video. Thanks!
I've studied many ressources on that subject, but it's finally on yours that I got the concept. Cheeeeeeeeeeeeers!!
The pigeon/Internet anecdote bears a striking resemblance the plot of Terry Pratchett's 'Going postal'
The best video after spending hours I finally understood the big O!Thanks
Straightforward. Easy to understand. Cool graphics! Hats off =)
HackerRank: Hi, Im Gayle Laakmann McDowell, author of Cracking the Coding Interview.
me: i am aware
I'm from SA. I remember this 'exercise'. My brother even did a cartoon about it :-)
Anyway, good explanation. Thanks.
Thank You for this video. I reached here after checking many other links .This is the best .
Really creative explanation for solidifying our basics. :)
I really love this video, they really did a great job here.
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!
Such a revolutionary explanation of Big O.
i need this type of teaching. Fun, understandable and useful.
Love your video! very clear and concise
Thank you sooo much for this...so to the point and simplified
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**
This is a wonderfully clear explanation.
Love your Graphics and Colors that are used for the Demonstration . makes it interesting to watch .
i agree!!!!!!!!
Thats a great explanation , supercrisp and helpful for interviews .
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 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?
Finally I understood Big O - Thanks a ton !!
Wtf.....watched so many videos to understand this concept....and here u are explaining the same topic in an easy way...❤️❤️
i love this woman, she helped me so much
props to the bumpy pigeon animation. I had a good chuckle. Also very good explanation
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.
We need some O(log n) and O(n log n).
Amazing explanation!! Please post more videos..
best lecture i have seen so far
You had to be an amazing note taker in school. Thanks for the explanation
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.
This is what I needed to level up thank you soo much.
Thanks , the concepts are now clear , time to solve questions
Well explained, thanks :)
Great explanation! Easy way to get it.
fav video for the concept..
gonna recommend to all my juniors.
Great explanation, thanks!
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
Great explanation, thank you
Great colors!😊
Very Good. Thanks from Brazil!
Great video, good theme the big O notation is very interesting
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 for the clear explanation
Thank you, it was really helpful.
amazing explanation. thank you
Really good explanation!
Very good explanation. Subbed!
Best explanation I've seen
Well explained about representing O as a function of N under different scenarios.
Great explanation!
Thanks so much, its life-saving
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!
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?
Thanks a lot, very informative :)
“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.
I studied this in my CS course 15 years back. After that I never got a chance to use it in practice.
Amazing video!
Thanks, great explanation :)
Just Great Explanation..
Thank you and it is really helpful.
I loved the story as well as the explanation. I also knew the pigeon is going to win:-)
Thanks for clear explanation ..
Good explanation. Thanks. :)
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
nice refresher, thanks
thank you! It really cleares stuff up :D
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
Very nice video!
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.
just what I needed
A simple thank you!
Wait so is Big O the function for runtime, or the speed of runtime increase (the derivative of runtime)?
3:20 Always good to see someone who knows how to draw a square...
it is a square, just not drawn to scale.
perspective
Nice point to highlight at 6:23 .. it's small but I caught out doing this in an interview before.
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?
great video thank you!
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)
7:13 function whyWhouldIDoThis(array) {return lol;}
Error: unused variable. 'array' is not used
So easy!!! I get it now!!!
Very well explained mam