Asymptotic Notations 101: Big O, Big Omega, & Theta (Asymptotic Analysis Bootcamp)
ฝัง
- เผยแพร่เมื่อ 27 ก.พ. 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Great Resource: cathyatseneca.gitbooks.io/dat...
Big O Cheat Sheet: bigocheatsheet.com
Today we will initiate a discussion on something that I have lied to you about for a very long time. This will be as simple as possible.
We will not only consider the informal definition but rather also look at the mathematical understandings behind why we call these asymptotic “bounds”.
Again, we care about this because the true colors of an algorithm can only be seen in the asymptotic nature of runtime and space.
So imagine this, we have these components:
A function T(n) which is the actual number of comparisons, swaps...just...resources an algorithm needs in terms of time or space. It is a function of n. When n changes, T(n) changes.
Our job is to classify behaviour.
A bound O( f(n) ) is the function that we choose to apply for the specific bounding.
The definitions, an example:
"T(n) is O(f(n))" iff for some constants c and n0, T(n) less than or equal to c * f(n) for all n greater than or equal to n0
In English...this means...we can say that f(n) is a fundamental function that can upper bound T(n)'s value for all n going on forever.
We have an infinite choice for what c is.
Our constant does not change behavior, it changes "steepness" of the graph.
We are saying that...if I declare f(n) as an upper bound, then I can find a constant c to multiply against f(n) to ALWAYS always always keep T(n) beneath my c * f(n)...T(n) will never beat c * f(n) for infinite n values...hence asymptotic bounding.
If we can't find this c then f(n) fails as an upper bound because it does not satisfy the asymptotic requirement.
So why are constants dropped?
Well...think about what we just did. The injection of the arbitrary c as a multiple onto a base function removes the need for a constant. It adds no meaning to a bound because it is conceptually already a part of the definition of what a bound is.
Big Bounds
Big O: Upper bound on an algorithm's runtime
Theta (Θ): This is a "tight" or "exact" bound. It is a combination of Big
For example:
An algorithm taking Ω(n log n) takes at least n log n time, but has no upper limit.
An algorithm taking Θ(n log n) is far preferential since it takes at least n log n (Ω(n log n)) and no more than n log n (O(n log n)).
Big Omega (Ω): Lower bound on an algorithm's runtime.
Little Bounds
Little o: Upper bound on an algorithm's runtime but the asymptotic runtime cannot equal the upper bound.
There is no little theta (θ).
Little Omega (ω): Lower bound on an algorithm's runtime but the asymptotic runtime cannot equal the lower bound.
If you can't get an exact upper bound, try lower bounding (although it is less useful to be honest).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
#asymptoticnotations - วิทยาศาสตร์และเทคโนโลยี
I really appreciate how you said at the beginning "Do you understand this? Because I don't, this is too thick for me, but this is the typical introduction you'd get in actual classes". This whole sentence resonated so much with me. Sometimes I cannot grasp those abstract ideas in math, and I just need to have the concepts explained to me like im 5 years old, and your video was able to make me understand this in just 20 minutes, when I've been struggling with this for 3 years. Thank you man, keep it up!
wanted to comment the exact same thing, HUGE thanks!!!!!
I had to pause the video to take the time to say this. Your videos are absolutely phenomenal. Keep up the good work man, your channel is 10x better than all the others I see that just tell you "how" to do something but don't go over the "why". Great stuff man, your channel will grow soon enough. Definitely recommending this channel to all my other friends.
thanks :)
I agree, I haven't seen videos so detailed and easy to understand. Most of the videos on TH-cam don't go this far into the small details that really help beginners build a foundation for their understanding.
@@momofro1819 absolutely
totally agree!
@@BackToBackSWE agreed
The day this guy stops making videos we'll be doomed.
hahahaha, that day has not come
@@BackToBackSWE Hope that day never comes.
@@TrendRain tru
Waaay doomed
@@susankanjira6098 hey
This is Ben from 5 months in the future. Cool video man.
This is Ben 1 month after this comment
@@BackToBackSWE Im doing this right now at university, you have no idea how much i smiled when you said "well this is too much to digest, lets take this line by line" , feels like that is always missing when trying to explain these types of concepts. Sub earned.
This is yash a student of IT. And here is a massive thanks for explaining the concepts.
This is my first comment I've ever written on TH-cam that I can recall. There is no better opportunity than to give you feedback as my first post.
I want to personally applaud you, not just for your excellent teaching (you a BEAST!), but the effort you take to thoroughly respond to all of your subscribers. That speaks volumes. This is what stood out to me aside from your incredible ability to convey these complex topics in an understandable way. You won my subscription.
What sets you apart from many other channels is how humble you are. You don't proclaim to be born as Knuth's twin brother or anything like that. You shared with us how you personally struggled with the same concepts that we now are an audience to. This quality makes you tangible. It draws people closer to you: "Hey! He was once where I was. I'm not alone. I can overcome these obstacles like he did!".
On that note, keep up the remarkable work. You have a gift and people out there in cyberspace are watching.
aw, haha, thanks. I hope I can help as many cyberspace people as possible in the coming years.
I rarely leave comments but thank you for explaining this like a normal person. I got overwhelmed with my textbook like it was purposely trying to prevent me from learning. You guys are phenomenal.
ye, bless da internet
I've been "kind of" getting these concepts for years, never quite being able to really get them. But I really understand now. Wow! I cannot believe it. Thank you!!! Some people are meant to be teachers. You are absolutely one of those. I agree with the others: you have a gift.
thanks, I am but a man
@@BackToBackSWE A talented and awesome man!
Hey man just wanted to thank you. Reviewing big O for my algorithms class and I am happy to say this is hands down the best explanation for this out there!
great
Absolutely amazing. Learnt more in 23 minutes than 1.5 hours of class. Looking forward to more such content!!
all I ask....please DONT ever stop making videos man...you are helping a lot of people with these vids
yep
This man literally called me out haha, I was scrolling to look at the comments and got off task and he said "you still with me" 4:57 and I was like yes sir.
lmaoooo
omg wtf. I actually understood this holy shit. You're amazing dude, wish you were my prof hahahahha
nice yo, u educamated now
I don't normally comment on youtube, but I had to say that you are a phenomenal teacher. Cannot thank you enough for how you explained this concept!!!
had to pause the video to say that the way you explain this is so refreshing. I thought it was going to be hard to understand but your explanation really helped. Thank you!!!
I'm writing this in the time of quarantine from my home and it's the first ever video I saw from your channel and I absolutely love this!!!!
I've been trying to figure out asymptotic notations since a long time and I finally got it for the first time ever.
TYSM for your hard work
ye, may u flourish
Pausing at 8:33 where it magically starts making sense to me, you are amazing! I dont comment often but you deserve a wide reach and endless growth, thank you for doing this!
Thankss! for more magic subscribe to our DSA course using the promo code "TH-cam40" for a 40% discount! - backtobackswe.com/pricing
I love you. Thank you, seriously bro you're an amazing person for taking the time to do these videos. No professor has ever explained it like you did
ye
I have paused at 15 minutes to say - thank you! This video helped me understand this topic very nicely.
I thought I was good at algorithms and data structures and time complexity stuff last year until they introduced this from a mathematical standpoint this year.
This really helped.
great
NOW We're talking! All those notations simply confused the heck out of me! Thanks for clearing that up! Now I know what they're all about! So helpful
lol nice and sure
This was legitimately the most helpful video I've ever seen. When my professor tried explaining this concept, it sounded like gibberish for 45 minutes. After watching this video, I completely understand the concept. Thank you so much for your help!
Wow, this is one of the best videos I have seen on this topic, you really break it down and speak in clear terms. Thank you so much! Keep up the great work.
sure
Absolutely love your videos! I've been studying this for a week and struggling, but after watching your video it all makes sense 🙌🏿
great to hear
Apart from Abdul Bari's asymptotic series, I have not come across any such well explained asymptotic analysis. You do it so well that it sticks in the mind forever. All my grey areas concerning Big O concept have been cleared. No need to claim anything. Well done; and keep it up!
dude for real this has to be one of the best youtube videos this year, thank you so much bro
hahahahaha, really?....r 👏e 👏 a 👏 l 👏l 👏y?
WOW! I spent 6+ hours watching different videos trying to figure out Big O and your video is the only one that makes sense to me. Thank you sooooo much
Happy to help
Have you tried the platform yet?
Check out the free DSA Mini-Course 👉backtobackswe.com/five-day
Table of Contents:
Introducing Asymptotic Bounding 0:00 - 0:46
Big O: The Asymptotic Upper Bound 0:46 - 1:05
Introducing Our Way of Thinking 1:05 - 1:40
What Does Asymptotic Mean? 1:40 - 2:39
Formally Defining Big O 2:39 - 5:35
This Is What I Mean By "Bounding" 5:35 - 8:05
This Bound Is Not Tight 8:05 - 8:55
Trying A Different Bound 8:55 - 12:06
Trying An Aggressive Bound 12:06 - 14:59
WHY DO WE DROP CONSTANTS? 14:59 - 16:11
Big Omega (Ω): The Lower Bound 16:11 - 18:40
Theta (Θ): The Exact Bound 18:40 - 21:37
Little o & Little Omega (ω) 21:37 - 22:08
Wrap Up 22:08 - 22:56
Errors:
I misspoke sometimes and reversed sentences...oh well, the point got across at least I hope.
There is no code for this video. Hey.
tks man, didn't understand fckn anything, but im seeing this video more times through this semstr.
Instablaster
Really really REALLY thankful that I stumbled onto this video. Your explanations are crystal clear and I can honestly say that I've never understood this subject matter as well as I do now having watched this video. I cannot thank you enough!
Amazing! Im a teacher trying to get his head around analytic number theory and felt like he needed to refresh his memory on Big-O notation. Gotta say, this one is great. It made it all much more intuitive. Now, whenever I see O(...) Im just thinking "O(...) = behaviour of the function under consideration". Thanks!
I cannot begin to explain how helpful this explanation was. Thank you so much for posting this!
Thank you so much for explaining this. As a graduate student in my 5th year of CS, I have only had bad luck with professors. No one would ever use examples or simplistic breakdowns to explain the concept, as you did in this video. You state the problem, simplify it, solve it, and work back up to the complex level we started at, in a way that makes it easy to understand, and very easy to follow. My assignments finally seem clear to me now. You've earned a sub :) Have a good week!
Nice!
You're a hero! This is much more understandable than my algorithms class!
thx
3 mins into the video was enough to make me subscribe. This guy knows his stuff!
i just needed to open my youtube acount and stop the video for a while to tell you that you made it easy and great ,and you're just the best one who explained that very well .thank you
Thanks man, I was about to drop my discrete math class. Watching your videos makes me actually understand the material rather than googling all the answers and not understanding them.
Just Wow!!! Really awesome work mate. I recently found your channel and it's become a habit now to search your playlist and find if you have a video on any doubt I have. Keep up the awesome work!
hahaha thanks
Just discovered your channel and I am so happy I did and grateful for you making these! Im a newbie still and these videos clear a lot of things up for me. Thanks!
Nice, thanks, and great
just a huge and great effort to explain the lesson, I really appreciate every single minute you spend making this video.. thank you so much the idea is getting clearer and clearer
I’m so glad I decided to watch some coding videos before bed. This is going to be tomorrow’s lecture and you are explaining it so well!
man!, i have been taking an online course in Algorithms, blv me lots of sources and videos that i did watch trying to get the meaning of different bounds, only your video which made me totally get it clearly and in a very smart easy way,, i can't thank you enough, keep up the good work.
nice
Dude, this is as clear as one can explain!! I feel like I understand everything now! Wow!! Great great great job!!!
thanks
First video of yours I’ve watched. This explanation made SO MUCH MORE SENSE than my professor. You’re awesome man!
thx
I am taking an algorithms class right now and this video helped me understand this topic SO much better. Thank you!!!
I swear this video explained everything so well. Thank you for the amazing content and have a good day
Wow, you are really a genius in explaining this stuff. I can't tell you how happy I am right now that I found your channel
i'm pretty normal and thx
Super helpful. Your way of explaining things is so clear. Keep up the channel!!
ok
Amazingly clear explanation. Literally felt the need to write a comment to thank you for making this!
thank you for watching, you are loved
That part where you talk about the function you get describing a behavior was very, very useful! Thank you! I was really missing that from the video lectures i was watching.
sure
You have no idea how this is helping me as a college student. I wish i can thank you in person but this is the best that I can do. Thank you so much for the video. I really appreciate it my man.
Fantastic video! I'm having to brush up on algorithms for grad school and this explanation is far superior than anything I was taught in my undergrad algorithms class. Thank you very much!
i usually dont comment in youtube . but i have to say this. this video has the best explanation of asymptotic bounding in the whole youtube !!! .... You are a remarkable and very knowledgeable teacher. thanks a lot !
Finallyyyyyyyy understood the topic!
Thank you!
sure
Never comment or like anyone TH-cam but this dude KNOWS what he's talking. and thank to him, I got every single point he explained super clear!
I never ever write youtube comments, but I just have to say that you are amazing. You explain concepts sooooo well. I would not be surviving in Data Structures 1 without you.
Thank you Back to Back SWE!
You will survive. And flourish. The internets are here for u.
You are really great at explaining complex CS stuff. This clip should be shown in every Algorithms Analysis course. Thank you so much!
Thank you so much ! I didn't really understand this last semester and now i finally get it !!! Explain so much better than the textbook
Thanks for breaking this down. You flipped the way I was thinking about big-O and now it makes sense with crystal clarity. Thank you very much.
sure
you speak very clearly, I understood everything perfectly thanks
Excellent video! Best explanation with great examples!
just want to say thank you for your clear explanation on Asymptotic Bounding. Been having trouble with it and this video explained it way better than any other video I have seen and as well better than the professor I have.
You just paraphrased 5 weeks of my university course and I understand this waaay more than I did previously. Every credit.
You're going in the right direction brother and so no one can actually stop this channel from becoming the most extensively used resource for all different levels of at sw engineers !
thanks lol
best and clearest explanation i've found for this concept! thank you so much!
Fantastic video! You explained something clearly that my professor could not.
thanks
Thanks for taking the time to teach us! I really want you to know that you definitely teach better than my professor
This was really helpful, thank you. I've already watched like four vids and this def helped me most
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
The Best Video out there! I must say your teaching style is great. It makes me feel like an older brother teaching and not an arrogant professor, lol. Keep up the good work!
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
Like others before me, I've also paused the video to just say thank you. Your explanation is absolutely wonderful and you being able to take on the point of view of a new learner and are able to successfully work from there, including the delivery and the understanding is nothing short of astonishing. I don't normally comment on tutorials because they rarely impress me, but really - great work. Wish my professors teached like this. Liked and subscribed.
sure! all the best friend
This is the best explanation I have seen of this topic on TH-cam. Thanks for helping out online students like me!
Happy Holidays 🎉 Thank you for your kind words, Kenneth! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
I don't normally leave comments, but I wanted to take the time to say thank you.
I have to say this is far clearer, more illustrative, and more understanding of the difficulty faced in digesting this topic than either my lecturer or the prescribed textbook (Shaffer) could muster.
Keep up the good work as it was excellent and now favourited.
I was so confused reading this topic in my textbook. You have made it so clear and simple. I will surely be watching more of your videos. Thanks so much
Kudos! subscribe to our high quality DSA based course using the promo code "TH-cam40" for a 40% discount! - backtobackswe.com/pricing
Dude, your videos are literally saving my life, Thank you sosososo much !
An absolutely brilliant explanation! U made this entire concept a lot easier! Thank you :)
You are helping me pass my classes
Dudeee.. i was trying to learn this topic since yesterday, but nothing worked and then i got your video in suggestion and boom, everything's clear. Thanks a lot
Dude we have homeworks that ask us to prove mathematically if a function is Big O, Big Omega or Theta of another function.
This video gave me a great intuition.
Keep up.
great and ok
You've taught me something in 20 minutes that my professor couldn't in 2 hours. Thank you so much, your videos are incredible
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Omg i dont know how to express my feelings now
You are such a great teacher and your way of explaining is the best i saw a lot of videos but no one gave me like you did
I really don't know what to say
Thank you so much
Dude, you are absolutely precise and amazing. Thanks man.
sure
This is the best explanation I have ever got on asymptotic notations. I will never forget this concept.
glad it helped
Thank you so much! I've been struggling with understanding this for the past 2 days, now I clearly get it thanks to this one video.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
Great job!! Very clear explanation.
bruh, you are f***** genius. I spent roughly about 7-8 hours truly understanding asymptotic bounding. You made it all clear. I see there are not many views in your channel, but keep it real, keep it simple you will eventually gonna make this the biggest and the best channel for CS student. Thanks for making things clear.
thnaks
your videos have improved. Your older vids I had to go at .75 speed, but now you talk clearer slower and its easier to understand. good job for improving
ye
Bless up man. I have an exam tomorrow and I definitely feel 100% confident about this topic.
nice
The best explanation of this subject I've seen 👏👏
Thank you for the help! I'm a intermediate programmer in Java/C++, as we have learned so far in the university for the 2nd grade, your videos helped me learn time complexities much better than it was taught in class. Keep up the good work!
wow man just wow the fact the you started out with big oh unlike all other teachers and even the book it self then went to omega all while building up for the main star 'theta' .... man ????!!!!!! after understanding the concept it only make sense to start this way what the hell is the book doing !!! you're soo good at teaching thank you so much 🤍🤍🤍 the thing that i like the most about your vids is that you explain 'the thing behind things' so it all make sense not just make it understandable and that is actully all it takes to make things understandable for lots of us
Thank you for your clear and thorough communication!! This was so easy to understand
Amazing thnx man EASY & CLEAR to understand 👌🏻
Keep up the good work man, your videos are really good. Best explanation I have found about this topic on TH-cam
thx
Finally someone that explains the theory behind big O. I am in a phase that I had to master the algorithmic analysis, (to some extent of course), and I spent an awful time of searching to find this part of theory. Everyone just assumes that we know this part and just throwing fancy words instead of explaining. I am grateful for your explanation.
great to hear, glad it helped
@@BackToBackSWE it did a lot :)
You are a great teacher, please continue with these videos! Subbed
The best video on this topic I've seen from TH-cam! Keep it up, plz!
thanks
i didn't understand Big O properly from being in university for 1 year, however after watching this video, i understand perfectly. You're Awesome!
great
This channel is under rated sadly. Keep up the good work.
Thank you SO much. I was struggling with this until I came across this video, you explain things so well.
Thank you for creating these videos. This one helped explain better than anything that I have learned in my class.
sure, enjoy and live a happy life :)
first video of your I watched but definitely not the last, great job!!
thanks and thanks
This is so damn good. It's so simple to understand while providing the deeper details of the topic. Thank you so much for this!
AMAZING VIDEO! I could not for the life of me understand big o from reading textbooks and from my lectures, but It finally clicked here. Cheers mate
nice