I have been struggling for hours to teach myself the concept of Big O notation in regards to Discrete Math...everything I have read and every example I have looked at was seemingly missing the gap between the theoretical idea of this concept and the actual problems that would be assigned. You cleared everything up in less than 7 minutes and taught me exactly what to do in order to solve this type of problem. I love you! You are wonderful! Thank you, thank you, thank you.
Just wanted to point out a calculation error for his example for Big Theta. @ n = 2, 5n^2 is 20, not 80. However, 5n^2 > 4n^2 + 16n + 2 @ n = 17, so the conclusion is still the same. F(n) is still Big-Theta(n^2).
While I noticed that to, your comment helped me notice a shortcut. It is 1 higher than 16 (in the 16n) so when doing proofs for this kind of quadratic equation that might be a useful starting point when testing proofs.
same thing here. it is obvious that in big theta example the rate of change of left function is higher than one of right function, so predicate evaluates to false
I found this through google interview university and this was very useful in helping me understand the formal definition as well as refreshing some of my math knowledge. Thank you.
love the explanation, on minute marker 22:36, you have n is 2, but when you plugged into 5n^2, you did n = 4 in your calculation. giving you 50 < 80 as true, when it's actually 5 * 2^2 or 5 * 4 which leads us to 50 < 20, which is false.
If it helps: Big O is like a big brother who says: whatever you do, you are never going to be better than me. omega is like your little brother who says, do whatever mischief you want to, but if you fall I will be there to catch you. theta is like your sister, who keeps switching sides, depending on what is at stake for the mischief- getting yelled at or candy.
my professor makes life so much harder than what it needs to be, he wrote set notation for everything and spent all kinds of time solving proofs. you jump right into the thick of it and make more sense than he ever will! thank you so much!
Great Job! I explain logs in much the same way, but yours was very concise! Don't fix the error, it helps students even more than your great explaination. It is motivating to students to look for errors, especially when made by 'the expert'. I plan errors within my lecture and give a headsup to a student who normally struggles with the material to act as a 'safety'. If noone else stops me and points out the error it is their job to 'notice' it.
What I like about this guy is that he looks and sounds as if he is figuring this out as he speaks. I like that because that is how I feel as I watch the video. He is mirroring my thought process. Anyway, you have managed to explain these concepts to me where the book has completely failed by over-complicating everything. Thank you!
I'm taking an algorithms class and I'm just expected to know this with little experience with these notations. The instructor showed one example and showed the graphs and that was it. The key thing I could not understand was WHY THIS MATTERS (which my instructor didn't really explain very well) and you cleared it up. Thank you.
I would like to thank you so much for putting this into plain English for me. The math itself isn't hard but my rusty math mind couldn't make sense out of the formal description. I also appreciate the table you set up. It made all the information I had floating around fall into the proper place and make perfect sense. I will be back to see more of your lectures as this data structure class progresses. Thanks again.
Been trying to get my head around this all day - reading and watching everything I could find, but went around in circles (too many very complex examples and/or jumping steps and leaving me scratching my head) - this was the first to make it clear - Great explanation, thanks greatly indeed!!!
***** Rosen's book is way too expensive, and not straight-forward. I've learned how to get to solutions faster by watching MIT opencourseware and this guy
that is correct, he did his math wrong. If it helps when finding values, you can use a graphing calculator such as the TI-84 and use it's table values to find the values.
thank u sir.. you save my life .. Hatts off... :) :) Thanks alot ... once again.. i m very happy that today i will learn about notations .. ... Brilliant ..
Please disregard all the comments about math corrections. People make mistakes and this is honestly one of the best lectures on this topic I have watched. Great job!
Great explanation for us autodidacts out there! I am taking an algorithm class at Stanford and was stuck on Big Oh notation. This should be added as optional material for the class. The video seems to abruptly end which leads me to think that there is a continuation video...true?
thank you for clear explaination. I fail this first course "data structure/algorithm" in college cuz i have problem understand the book and the professor that year. Thanks again.
How did you come up with n to the power 4 when the equation is quadratic? I think f(n) less than O(g(n)) when g(n) = n ~2 for all n greater than 0 and some constant c,
You said that 3logx(n) is the same as logx(n)^3 (at 46:22). I'm pretty sure that's not true. Here's an example where that's not true; log10(100) = 2. 3*2=6 2^3 = 9 Is there something I'm missing when you said that you can turn the constant in front of a log into it's exponent, or is the exponent supposed to go somewhere else? Maybe you meant 3logx(n) = logx(n^3). I think that would be true. 3log10(100) = 6 log10(100^3) = log10 (1000000) = 6 Okay, so that's what you meant, you just didn't explain it well and wrote it wrong :D
Log (n^3) = 3 log n Log (1000) = log (10^3) = 3 log 10 = 3 If he put the "^3" elsewhere, then it may be saying something different. But it's usually what I'm referring to here.
at the indicated point he had Log(n)^3, not Log(n^3). He erased the 3 from before the log and put it in an exponent after the bracket. In my post, I realised that and showed that Log(n^3) is probably what he meant - and I don't think it changes his proof, it's just written incorrectly.
Couldn't understand anything during my lecture class but now I am like " Wow it's not that difficult !" .. Thanks alot for the video .. Great one though
Nailed it! Thank you for the insight, I just started learning computer science or software development, I am sure with this foundation, I will make it even if I am already an old punk🤣😎
I have been struggling for hours to teach myself the concept of Big O notation in regards to Discrete Math...everything I have read and every example I have looked at was seemingly missing the gap between the theoretical idea of this concept and the actual problems that would be assigned. You cleared everything up in less than 7 minutes and taught me exactly what to do in order to solve this type of problem. I love you! You are wonderful! Thank you, thank you, thank you.
Just wanted to point out a calculation error for his example for Big Theta. @ n = 2, 5n^2 is 20, not 80. However, 5n^2 > 4n^2 + 16n + 2 @ n = 17, so the conclusion is still the same. F(n) is still Big-Theta(n^2).
While I noticed that to, your comment helped me notice a shortcut. It is 1 higher than 16 (in the 16n) so when doing proofs for this kind of quadratic equation that might be a useful starting point when testing proofs.
ur right thanks for confirming it did not make sanse n=2 5n^2 = 20 is 80
xXAlphaXx Thanks for pointing that out. Threw me off for a second.
Thank you.
same thing here. it is obvious that in big theta example the rate of change of left function is higher than one of right function, so predicate evaluates to false
I found this through google interview university and this was very useful in helping me understand the formal definition as well as refreshing some of my math knowledge. Thank you.
"Make Everything as simple as possible, but not simpler"....this video taught me what a whole chapter could not. Thanks, this was great!
love the explanation, on minute marker 22:36, you have n is 2, but when you plugged into 5n^2, you did n = 4 in your calculation. giving you 50 < 80 as true, when it's actually 5 * 2^2 or 5 * 4 which leads us to 50 < 20, which is false.
Best video I've been able to find anywhere on the net. Simply put and easy to understand.
If it helps: Big O is like a big brother who says: whatever you do, you are never going to be better than me.
omega is like your little brother who says, do whatever mischief you want to, but if you fall I will be there to catch you.
theta is like your sister, who keeps switching sides, depending on what is at stake for the mischief- getting yelled at or candy.
And log is like the poo in between
Hi @Mitch, I used your comment in one of my posts on "Complexity analysis of an algorithm". Here: link.medium.com/PTAKZzddR5
@@akshitzaveri224 nice. thanks
I think this is the most valuable explanation of big O notation I've come across on UA-cam so far! Thanks a mil!
my professor makes life so much harder than what it needs to be, he wrote set notation for everything and spent all kinds of time solving proofs. you jump right into the thick of it and make more sense than he ever will! thank you so much!
Thank you so much for explaining this. So many have tried and they have failed. You Sr. are an instructor. I thank you again.
You helped me finally get a handle on Big O notation. Something my instructor and textbook failed to do.
Thanks so much!
Best Tutorial I have watched for Big-Oh. You explain it expertly
you're the first person to explain to me why we're actually looking for a c and a n0,thank you.
thank you I have been struggling with asymtotic notation for a while now and this video is the first to thoroughly explain it.
Brilliantly done. I wish my algorithms lectures were this clear.
Thank you for working through the example problems, this is the tenth tutorial I've watched and the first one to be successful.
Great Job! I explain logs in much the same way, but yours was very concise! Don't fix the error, it helps students even more than your great explaination. It is motivating to students to look for errors, especially when made by 'the expert'. I plan errors within my lecture and give a headsup to a student who normally struggles with the material to act as a 'safety'. If noone else stops me and points out the error it is their job to 'notice' it.
watching this guy struggle with 5*4 literally killed my brain
Despite a small screw up at 23 this guy has done a great job explaining it all.
What I like about this guy is that he looks and sounds as if he is figuring this out as he speaks. I like that because that is how I feel as I watch the video. He is mirroring my thought process. Anyway, you have managed to explain these concepts to me where the book has completely failed by over-complicating everything. Thank you!
I'm taking an algorithms class and I'm just expected to know this with little experience with these notations. The instructor showed one example and showed the graphs and that was it. The key thing I could not understand was WHY THIS MATTERS (which my instructor didn't really explain very well) and you cleared it up. Thank you.
I would like to thank you so much for putting this into plain English for me. The math itself isn't hard but my rusty math mind couldn't make sense out of the formal description. I also appreciate the table you set up. It made all the information I had floating around fall into the proper place and make perfect sense. I will be back to see more of your lectures as this data structure class progresses. Thanks again.
Briliant, thank you very much for this clear explanation. Found it through Coding Interview University, super helpful!!!!
Thank you for this easy, simple explanation. I was searching all over the web for something like this
u sir are a savior , ur lectures are much clearer then any textbook or teacher ive had. thanks!
Been trying to get my head around this all day - reading and watching everything I could find, but went around in circles (too many very complex examples and/or jumping steps and leaving me scratching my head) - this was the first to make it clear - Great explanation, thanks greatly indeed!!!
Thank you sir! I have a big discrete maths exam coming up at Michigan and this has been much more helpful than any of my professors.
Infact, I would purchase your Discrete textbook (unlike the Rosen pdf sitting on my desktop...)
***** Rosen's book is way too expensive, and not straight-forward. I've learned how to get to solutions faster by watching MIT opencourseware and this guy
In the big theta example, the 5n^2 doesn't overpower the 4n^2+16n+2 until n=17.
that is correct, he did his math wrong. If it helps when finding values, you can use a graphing calculator such as the TI-84 and use it's table values to find the values.
You are the best lecturer Prof. Thanks.
Thank you so much for taking so much time and effort. It really shows and it's very helpful.
at 22:30 5n^2 = 20 not 80
7:23, actually, the letter "O" we use comes directly from the Greek letter Omicron: "O".
Dude, you da real MVP. I get it now...unreal.
Thank you very much for posting this. Best lecture on this topic I have seen!
I really enjoyed this video. Thanks for describing the topic very simply.
You are an excellent teacher.
The clearest explanation ever.
Just a little confused at 46:34, "the third case", did you mean "x>y"?
thank u sir.. you save my life .. Hatts off... :) :) Thanks alot ... once again.. i m very happy that today i will learn about notations .. ... Brilliant ..
Thank you! Very easy to understand and a lot more clear than my textbook and professor!
Please disregard all the comments about math corrections. People make mistakes and this is honestly one of the best lectures on this topic I have watched. Great job!
Great stuff. They use this as a link in my university Algorithm class! ;)
Thank you, thank you, thank you for this simply and clear explanation!
Thank you. This explanation really helped me grasp better this topic.
The explanation is brilliant!
Can you Sir please explain how 5n^2 = 80 for n=2. It should be 20. you can see it at 22:44 min
I noticed the same mistake. The answer has a few more steps than choosing n to be 2.
Would love to take one of your classes. Thanks for uploading this!
this is the best lesson ive had on this topic . Thank you so much !! I finally understand
thankyou for the very patient and learned teaching... really helpful!!
Could you please add caption here? I'm deaf and i can't hear what you said. If you add it, it would be appreciated for our community
unless I am not understanding this correctly -- isn't 5n^2 = 20 when n = 2 and not 80 ?
It is better if we are able to skip that part, to err is human...but the concept was awesome
you made a mistake in 22:20 5*2^2 =20
Thank you so much for such comprehensive explanation, Great Job!
THANK YOU, been looking everywhere for a good explanation for this =]
This is the best lecture on this topic thanks
last minute cramming for final, thank you sir
This is the video that finally did it for me, thank you so much!
Thank you so much for the clear explanation, it's really helpful... i wish you could do more on Algorithms.
very nice explanation. thank you a million.
Prof Bill Byrne! Monmouth University. Great to see you sir!
Thanks so much, covers all required basics of my algorithms class!
23:00, For Theta, c=5, n=17 for that statement to be true. n=2 was wrong.
Yeh you can just solve 4n^2 + 16n + 2 = 5n^2 and get n_0
I KNEW IT
This was perfect! Thank you professor and shout out to Russell Tepper.
at 23:00 the n0 must be>= 17 :) thanks for this great lecture!
Great explanation for us autodidacts out there! I am taking an algorithm class at Stanford and was stuck on Big Oh notation. This should be added as optional material for the class. The video seems to abruptly end which leads me to think that there is a continuation video...true?
Extremely helpful video! The textbook I am using just over complicates everything.
thank you for clear explaination. I fail this first course "data structure/algorithm" in college cuz i have problem understand the book and the professor that year. Thanks again.
Thank you so much!!!! You made this very easy to understand and explained it very well
sit, you are amazing teacher
12:18 i couldnt make sence why f(n) => Omega(n^3) answer is no. cause 4 < Cn? plz teech me...
How did you come up with n to the power 4 when the equation is quadratic? I think f(n) less than O(g(n)) when g(n) = n ~2 for all n greater than 0 and some constant c,
Awesome Tutorial Very Helpful
For the theta example : n_0 = 17
I cannot thank you enough for this video :-) Very clear explanation
Awesome! That helped me so much. Thank you.
Thank you so much for making this video! This helped me a lot
Thats a really clean tutorial..
which is the time complexity of the following sequence? and why?
int n, i, j, k, s=0;
cin>>n;
for(i=1; i
Great content, thanks for this!
You said that 3logx(n) is the same as logx(n)^3 (at 46:22). I'm pretty sure that's not true. Here's an example where that's not true;
log10(100) = 2.
3*2=6
2^3 = 9
Is there something I'm missing when you said that you can turn the constant in front of a log into it's exponent, or is the exponent supposed to go somewhere else?
Maybe you meant 3logx(n) = logx(n^3). I think that would be true.
3log10(100) = 6
log10(100^3) = log10 (1000000) = 6
Okay, so that's what you meant, you just didn't explain it well and wrote it wrong :D
Log (n^3) = 3 log n
Log (1000) = log (10^3) = 3 log 10 = 3
If he put the "^3" elsewhere, then it may be saying something different. But it's usually what I'm referring to here.
at the indicated point he had Log(n)^3, not Log(n^3). He erased the 3 from before the log and put it in an exponent after the bracket.
In my post, I realised that and showed that Log(n^3) is probably what he meant - and I don't think it changes his proof, it's just written incorrectly.
I feel like Recursive loop are the best example of everything he told here.
Awesome explanation!
omg finally I've got that - thx a lot!!!
Couldn't understand anything during my lecture class but now I am like " Wow it's not that difficult !" .. Thanks alot for the video .. Great one though
This is awesome! Thank you!
Best explanation ever, thanks!
much better than my professor, thx
Thank you! You did what my prof couldnt! :)
get 2*2 wrong?
@@natehoulihan524 :D
You're awesome man
Extremely helpful. Thank you
Nailed it! Thank you for the insight, I just started learning computer science or software development, I am sure with this foundation, I will make it even if I am already an old punk🤣😎
Nice Explanation. Helped me !
best explanation ever
thank you very nuch for this lecture, it helped me a lot to understand many things, now things make sense for me :)
oh! very nice explanation. Thank's a lot.
Thank you for saving me 10 hours
Very helpful video. Thanks a lot.
You made this perfectly clear, thank you so much!
excuse me. What is the difference if we define n>=n0 instead of n>n0? Is the big O notation still correct? Thank you
Great video. Thank you.
Awesome video!