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 UA-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.
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!
This is my first comment I've ever written on UA-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
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
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!
omg wtf. I actually understood this holy shit. You're amazing dude, wish you were my prof hahahahha
nice yo, u educamated now
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
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
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!
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!
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!!!
all I ask....please DONT ever stop making videos man...you are helping a lot of people with these vids
yep
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!
Absolutely amazing. Learnt more in 23 minutes than 1.5 hours of class. Looking forward to more such content!!
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
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
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.
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!!!
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.
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 am taking an algorithms class right now and this video helped me understand this topic SO much better. Thank you!!!
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!
You just paraphrased 5 weeks of my university course and I understand this waaay more than I did previously. Every credit.
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!
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
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
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 "UA-cam40" for a 40% discount! - backtobackswe.com/pricing
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, 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
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.
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
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'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
3 mins into the video was enough to make me subscribe. This guy knows his stuff!
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
my professor took 4 classes to explain this in a way that didn't make sense and then I found this video and understood the concepts in 23 minutes, you sir are a legend
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
I cannot begin to explain how helpful this explanation was. Thank you so much for posting this!
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!
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.
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
Pretty late here ,but I had a subject on this topic this year where I was really confused on the lectures, and this really cleared things up for me, especially I am the type who learns from clear examples and this just gave me what I need, thanks lots.
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
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
Never comment or like anyone UA-cam but this dude KNOWS what he's talking. and thank to him, I got every single point he explained super clear!
Since I am into hardware electronics, I don't use this type of mathematics for programing algorithms, and I just came to youtube to get the definition for the word asymptotic. However I found this guy sooo intelligent and able to convey complex mathematics in a way that I could understand much of it, even though it is outside the realm of what mathematics I ordinarily use!! Outstanding lecture on this subject matter!!
great, thank you.
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
You are really great at explaining complex CS stuff. This clip should be shown in every Algorithms Analysis course. Thank you so much!
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
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
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 !
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
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 😀
I usually don't comment for videos, but this video, which is the first one I've seen from this channel, shows how clearly you can make complicated topics be understood.
and I think I owe you a thank you.
👍
Hey, thanks
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
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!
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're a hero! This is much more understandable than my algorithms class!
thx
First video of yours I’ve watched. This explanation made SO MUCH MORE SENSE than my professor. You’re awesome man!
thx
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 "UA-cam40" for a 40% discount! - backtobackswe.com/pricing
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
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
Thank you so much for this video. I have been pulling my hair out trying to learn this thing, i almost accepted the fate that i might fail this subject again, but you have actually given me some hope that i can finish this task! thank you.. i actually understand it now im glad i invested the 24 minutes to watch this. It makes so much sense
You can pass and do whatever u want
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
Dude, this is as clear as one can explain!! I feel like I understand everything now! Wow!! Great great great job!!!
thanks
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
Amazingly clear explanation. Literally felt the need to write a comment to thank you for making this!
thank you for watching, you are loved
Finallyyyyyyyy understood the topic!
Thank you!
sure
Seriously, I have exam in next 36 hours, kinda memorized these notations for different sorting algorithms and now angry at myself for why I didn't come across this video at the beginning of studying this subject. But I am happy too, better late than never. Thank You a million times for this superb easily taught complicated things :)
This is the best explanation I have ever got on asymptotic notations. I will never forget this concept.
glad it helped
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
You are the best teacher. I have finished computer science University and thought that complexities are some king of black magic. But you put the information in such a great way that you cannot not understand. Thank you so much for videos! And wish you a happy life!
haha thanks, wish u a happy life 2
Wow this makes so much sense. I'm in a discrete math course right now and my professor didn't explain any of this. He just threw identities at us an expected it to stick.
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
you speak very clearly, I understood everything perfectly thanks
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/ 🎉
Dude, your videos are literally saving my life, Thank you sosososo much !
Half way through the video I just started laughing out loud and clapping into my hands because I couldn't believe that I finally understood what I never quite truly managed to understand. This is the best explanation of asymptotic bounding that I have ever heard and all I can say is thank you a million times!!
I rarely write youtube comments, my comments are mostly sarcasm, but THANK YOU SO MUCH for making this easier to understand. People like us need to understand with the flow like a story, and you did exceptional job in that! :)
You are helping me pass my classes
this is literally the best video anyone can watch that explains asymptotic notations if they have no background
Glad we could help
I swear this video explained everything so well. Thank you for the amazing content and have a good day
It took this video to make me realize that my understanding of what something like `f(n) = O(g(n))` means was completely backwards. I thought it meant that f(n) must be larger than g(n), but nonono. Whatever g(n) is needs to be larger than f(n).
Wish I'd seen this before my last assignment. Glad I saw it before the first exam. Great video!
You can explain in 23 minutes what my profesor couldn‘t in multiple lectures - thank you so much!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
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 😀
Man out here teaching better than the top universities in the world, for free and in less time. Free vs few thousand dollars per class, 23mins vs 3 hour lecture unnecessarily complicating what is already unintuitive. Absolute champion!! If you were an algorithm, you'd be O(1)
This is the best explanation I have seen of this topic on UA-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
Hey man, I don't usually comment on videos but this is some solid content. I definitely understood it by the first 10-12m but continued watching cause of how straightforward you explain things. Definitely learned more about this than 2 of my 50m lectures.
nice
Excellent video! Best explanation with great examples!
The best explanation of this subject I've seen 👏👏
This is the best description of this topic I've ever seen. Awesome! Thanks for the killer content.
sure
This is by far the best explanation I've seen on this topic.
hey
Bruhhhh.....all the Computer Science classes I've taken thus far and have PAID for and this dude just taught me Big O, Big Omega, and Theta way better than any of them did.......in 23 minutes......on UA-cam.....for free.
I was so frustrated with the book I've been reading for not explaining this thoroughly. Thanks for this
Great job!! Very clear explanation.