Table of Contents: Quick Intro 0:00 - 0:22 For Loop Madness 0:22 - 0:31 What Does Asymptotic Really Mean? 0:31 - 1:27 Tail Behavior 1:27 - 1:48 Why Elapsed Real Time Is Unreliable 1:48 - 2:31 What We Should Be Interested In 2:31 - 2:55 Racing 2 Computers 2:55 - 3:40 Who Will The Winner Be? 3:40 - 3:52 The Approximate Running Times 3:52 - 4:28 Investigating Linear Functions 4:28 - 5:28 The Graphs Share Something In Common 5:28 - 6:14 Why Do We Drop Constants? 6:14 - 6:40 What I Really Mean When I Say "Linear" Time 6:40 - 7:03 Wrap Up 7:03 - 7:45 Notes: 0:28 -> For those curious, the work that the 2 for loops do would be bounded by O(n). This is because for each of the n iterations of the outer loop, we will perform 10 iterations in the inner loop...do you notice how n does not influence the inner loop? In fact, we notice that the work of 10 (from the inner loop) for each of the outer loop iterations is...constant. Constant in time......O(1) time. So O( n * 1) = O(n). Where n is a measure of an arbitrary input. 2:54 -> Credits to Clyde Kruskal & Mohammad Nayeem Teli (both teachers at the University of Maryland) for the example of Computer A & computer B running 2 different algorithms. That was not an example that I created myself. 5:01 -> no idea why the video looks faded out...camera was acting weird. 6:40 -> Big O is only 1 way we can bound tail behavior. There are others.
There are too many sites that try to give a quick crash course a month or two months before the interview, but I really like how dive deeper and take your time to explain things. Also love the fact that your content is more academic in nature. Thank you for your hard work man, its much appreciated, def gonna check out your platform.
Happy Holidays 🎉 Thank you for your kind words! 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
Absolutely phenomenal. I just wish you applied examples, to show us how you find the notations. Too bad you didn't cover Recurrence relations as well :(
yo man thanks for blessing up with such informative videos. Your Asypmptotic videos cleared so many confusions. Just one thing, can you make a video explain how to add and mull algos. Like how do we know by analysing algos if its linear,quad,log, n log n etc
hey bro, i wanna learn asymptotic and bigo notation completly. i watched your video it help me. but i want learn completly. could u suggest books or link or make a complete playlist on it. btw u r awesome in explain topics.
I made a video on it a while back but it was badly shot and badly edited (you can find it on the channel). I will redo it but that video (if you can bare the bad quality lighting) is pretty exhaustive.
@@BackToBackSWE ok i will try or why you not planing to shoot it again. in my college time bigo notation is hard to understand. but now atleast i am understanding it. what is the actual meaning of log(n). Thanx
Hi, Let's say I was going through a list of numbers and "offering" them into a priority queue whose offer function is log(n), Will this be n*log(n) because I'm doing a log(n) operation n times or will it just be O(n) because the operation itself doesn't matter since the algorithm runs n times? I think I saw you say something about algorithmic complexity vs runtime complexity in one video but I couldn't find it again lol
Since you do n operations that take O(log(n)) time it will take O(n * log(n)) time. This does not pertain to heapsort. For heapsort, building the heap takes ϴ(n) time and the extraction phase happens roughly n times and each extraction of the min/max element takes O(1) time (we just pull it from index 0 in the array representing our heap) and then the heapification "downward" of the element swapped to the root will take O(log(n)) time. So yeah, for what you said, O(n * log(n)).
If someone asks you what is the asymptotic solution of a given problem? don't tell him a definition of the asymptotic solution instead tell him that at this arbitrary boundary condition 'a' our model should give us an already known solution 'y'. This known solution is maybe from previously developed models or from experiments. Thoughts?
Table of Contents:
Quick Intro 0:00 - 0:22
For Loop Madness 0:22 - 0:31
What Does Asymptotic Really Mean? 0:31 - 1:27
Tail Behavior 1:27 - 1:48
Why Elapsed Real Time Is Unreliable 1:48 - 2:31
What We Should Be Interested In 2:31 - 2:55
Racing 2 Computers 2:55 - 3:40
Who Will The Winner Be? 3:40 - 3:52
The Approximate Running Times 3:52 - 4:28
Investigating Linear Functions 4:28 - 5:28
The Graphs Share Something In Common 5:28 - 6:14
Why Do We Drop Constants? 6:14 - 6:40
What I Really Mean When I Say "Linear" Time 6:40 - 7:03
Wrap Up 7:03 - 7:45
Notes:
0:28 -> For those curious, the work that the 2 for loops do would be bounded by O(n). This is because for each of the n iterations of the outer loop, we will perform 10 iterations in the inner loop...do you notice how n does not influence the inner loop? In fact, we notice that the work of 10 (from the inner loop) for each of the outer loop iterations is...constant. Constant in time......O(1) time. So O( n * 1) = O(n). Where n is a measure of an arbitrary input.
2:54 -> Credits to Clyde Kruskal & Mohammad Nayeem Teli (both teachers at the University of Maryland) for the example of Computer A & computer B running 2 different algorithms. That was not an example that I created myself.
5:01 -> no idea why the video looks faded out...camera was acting weird.
6:40 -> Big O is only 1 way we can bound tail behavior. There are others.
There are too many sites that try to give a quick crash course a month or two months before the interview, but I really like how dive deeper and take your time to explain things. Also love the fact that your content is more academic in nature. Thank you for your hard work man, its much appreciated, def gonna check out your platform.
Sure!
Best Explanation EVER!!!! I Mean it! ASYMPTOTICALLY
thanks
bro ur better than 99% of the online educators and even some professors!
Thank you SO MUCH! The best introduction to this concept that I have come across.
Wow this was so clear! I love the graphics popping in and out and the way your voice inflections keep us alert. Great teaching skills!
Happy Holidays 🎉 Thank you for your kind words! 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
Two years in college and it wasn't this clear for me.....Thanks, man!
nice.
I am getting started with algorithms.Still confused but this video made it a little more clearer. Good job bro
Absolutely phenomenal. I just wish you applied examples, to show us how you find the notations. Too bad you didn't cover Recurrence relations as well :(
thanks and yeah
Your channel is a lifesaver for self-taught programmers...
Thank You!!
Do check out backtobackswe.com/platform/content
Thank you for the examples that you used. This is such a good and less scary introduction to time complexity analysis
did I understand shit? nah
did I enjoy this due to your fun energetic personality? hella
that's what it's all about
I was having a problem with understanding what "asymptotic" really mean and you helped me ..thank you very much
Boyyy YOU GOING CRAZY. Great Explanation!
Thank you so much for helping me understand this concept, this was a great explanation.
This made it indeed clearer! Thanks a lot
nice
By far the best explanation I have encountered!
nice
yo man thanks for blessing up with such informative videos. Your Asypmptotic videos cleared so many confusions. Just one thing, can you make a video explain how to add and mull algos. Like how do we know by analysing algos if its linear,quad,log, n log n etc
haha nice, yeah I'll do that
Very good! Of course I Subscribed. I was looking for a function of asymptotic penetration in quantum immersion and you made it very clear. Thanks.
thx and thx
Great explanation
hey bro, i wanna learn asymptotic and bigo notation completly. i watched your video it help me. but i want learn completly. could u suggest books or link or make a complete playlist on it.
btw u r awesome in explain topics.
I made a video on it a while back but it was badly shot and badly edited (you can find it on the channel). I will redo it but that video (if you can bare the bad quality lighting) is pretty exhaustive.
@@BackToBackSWE ok i will try or why you not planing to shoot it again. in my college time bigo notation is hard to understand. but now atleast i am understanding it. what is the actual meaning of log(n).
Thanx
Excellent ! I haven't come across such a fantastic explanation so far !
How did you come up with the 5.5 hours and 20 minutes? Where did you get those values from?
Thanks, you explain very clear.
sure!
that is very very good explanation
You are doing such an amazing job, keep them video coming...
ok
I really love your videos. Thanks so much for clarifying so many black knowledge holes 🕳 for me!
That's a great explanation
such a clear explanation! thanks!!
sure
love the energy !
ohh my f god! this was so quick, yet so helpful. thank you so much!
Thank you, means a lot 🎉 You can also check out our free DSA course - backtobackswe.com/
Thank you so much for such a clear explanation :)
sure
Thank you very much!
Good explanation
Thanks
sure
Always a pleasure to watch your video 😇.
Fantastic video, love the ending 😂
I wasn't looking for this video and stumbled into it.
Your first graph is incorrect.
It should be 1/x^2
Hope this helps
you are the GOAT
a really great job
thx
Awesome :) Thanks for this.
sure
Thanks!
Helpful!
Thanks
sure
Thank you!
sure
I really appreciate this explanation because you made a point to explain why asymptotic complexity is important
thank you!
Subscribing is a MUST!
thanks haha
Great explanation!
This is mind blowing how you explained it. Keep it up. I subed asap.
For your 100k milestone
Ye
Aaaaaahhhaaaaa!!! I just got it!!! Thanks, man! :D
cool
Back To Back SWE Yes, you have contributed greatly to my Mad Ninja Skills! :D Thank you!!
what is "li code" that he talks about at 2:00 ?
Wow! It's was very clear (a little bit more clear than Udi Manber(1989) hahaha).
great
Thanks 🙏🙏
Good video
Bro thanks
Thanku......
thank u
A very humongous thanks to you 🙌
yw
Hi,
Let's say I was going through a list of numbers and "offering" them into a priority queue whose offer function is log(n),
Will this be n*log(n) because I'm doing a log(n) operation n times or will it just be O(n) because the operation itself doesn't matter since the algorithm runs n times? I think I saw you say something about algorithmic complexity vs runtime complexity in one video but I couldn't find it again lol
Since you do n operations that take O(log(n)) time it will take O(n * log(n)) time. This does not pertain to heapsort. For heapsort, building the heap takes ϴ(n) time and the extraction phase happens roughly n times and each extraction of the min/max element takes O(1) time (we just pull it from index 0 in the array representing our heap) and then the heapification "downward" of the element swapped to the root will take O(log(n)) time.
So yeah, for what you said, O(n * log(n)).
Amazing
thanks
Do some examples!!!
ok
Be kind, man!
damn that was good. thanks.
sure
salamuch homie
Wow!!
yes
U r champ
If someone asks you what is the asymptotic solution of a given problem? don't tell him a definition of the asymptotic solution instead tell him that at this arbitrary boundary condition 'a' our model should give us an already known solution 'y'. This known solution is maybe from previously developed models or from experiments. Thoughts?
This video must have been shot on the 13th of October...
why
cool
Yep reality is computer code basically holy crap awkward😮
I liked the video, but it was not too clear. You can do it better
ok haha