Big O Notation
Vložit
- čas přidán 26. 09. 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...
- Věda a technologie
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?
Thanks so much, this 8 minute video made it way more clear than several hours of lectures and readings
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.
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.
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.
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.
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 :-)
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
oh my god for the first few minutes I thought it is an ad.
lol me too
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.
HOLY SHIT, THANK YOU SO MUCH. So wish you were my lecturer cause this made so much more sense than anything he ever said!
The best video after spending hours I finally understood the big O!Thanks
Excellent explanation! Thanks for simplifying Big O concepts.
I've studied many ressources on that subject, but it's finally on yours that I got the concept. Cheeeeeeeeeeeeers!!
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'm from SA. I remember this 'exercise'. My brother even did a cartoon about it :-)
Anyway, good explanation. Thanks.
Such a revolutionary explanation of Big O.
Wtf.....watched so many videos to understand this concept....and here u are explaining the same topic in an easy way...❤️❤️
A very concise and to-the-point video. Thanks!
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!
Thank You for this video. I reached here after checking many other links .This is the best .
I enjoyed this. As a person who didn't have a background in Math or CS, this was very understandable. Now, I just need to remember and practice.
i need this type of teaching. Fun, understandable and useful.
The pigeon/Internet anecdote bears a striking resemblance the plot of Terry Pratchett's 'Going postal'
Straightforward. Easy to understand. Cool graphics! Hats off =)
i love this woman, she helped me so much
This is a wonderfully clear explanation.
Love your Graphics and Colors that are used for the Demonstration . makes it interesting to watch .
i agree!!!!!!!!
I really love this video, they really did a great job here.
Really creative explanation for solidifying our basics. :)
You had to be an amazing note taker in school. Thanks for the explanation
Finally I understood Big O - Thanks a ton !!
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
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.
best lecture i have seen so far
props to the bumpy pigeon animation. I had a good chuckle. Also very good explanation
Thank you sooo much for this...so to the point and simplified
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!
fav video for the concept..
gonna recommend to all my juniors.
Thats a great explanation , supercrisp and helpful for interviews .
Love your video! very clear and concise
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.
Thanks , the concepts are now clear , time to solve questions
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?
Very Good. Thanks from Brazil!
Great explanation! Easy way to get it.
Amazing explanation!! Please post more videos..
Well explained about representing O as a function of N under different scenarios.
“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.
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**
HackerRank: Hi, Im Gayle Laakmann McDowell, author of Cracking the Coding Interview.
me: i am aware
Best explanation I've seen
This is the clearest intro on Big O
Great video, good theme the big O notation is very interesting
Thanks so much, its life-saving
Great explanation, thanks!
Well explained, thanks :)
Very good explanation. Subbed!
Great explanation, thank you
thank you for the clear explanation
Thank you, it was really helpful.
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
Great colors!😊
amazing explanation. thank you
I loved the story as well as the explanation. I also knew the pigeon is going to win:-)
thank you! It really cleares stuff up :D
Really good explanation!
Thanks a lot, very informative :)
Thank you and it is really helpful.
Great explanation!
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?
nice refresher, thanks
Just Great Explanation..
Thanks, great explanation :)
A simple thank you!
Thank you very much, better than my CS PhD. Professors.
Finally a good explanation! Couldn't understand it with my lazy ass teacher... Thank you!
Amazing video!
Thanks for clear explanation ..
We need some O(log n) and O(n log n).
I studied this in my CS course 15 years back. After that I never got a chance to use it in practice.
Good explanation. Thanks. :)
I appreciate the bird moving at the end. Fun touch.
Very nice video!
just what I needed
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 examples thank you
Nice point to highlight at 6:23 .. it's small but I caught out doing this in an interview before.
great video thank you!
The easiest explanation about Big O in the internet so far.
Thank you so much!
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