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.
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
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?
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)).
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
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.
Best Explanation EVER!!!! I Mean it! ASYMPTOTICALLY
thanks
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!
did I understand shit? nah
did I enjoy this due to your fun energetic personality? hella
that's what it's all about
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
Thank you SO MUCH! The best introduction to this concept that I have come across.
Two years in college and it wasn't this clear for me.....Thanks, man!
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
I am getting started with algorithms.Still confused but this video made it a little more clearer. Good job bro
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
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
How did you come up with the 5.5 hours and 20 minutes? Where did you get those values from?
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
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?
You are doing such an amazing job, keep them video coming...
ok
This made it indeed clearer! Thanks a lot
nice
Yep reality is computer code basically holy crap awkward😮
Wow! It's was very clear (a little bit more clear than Udi Manber(1989) hahaha).
great
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)).
that is very very good explanation
Fantastic video, love the ending 😂
Awesome :) Thanks for this.
sure
what is "li code" that he talks about at 2:00 ?
That's a great explanation
such a clear explanation! thanks!!
sure
Thank you very much!
This video must have been shot on the 13th of October...
why
Thank you so much for helping me understand this concept, this was a great explanation.
Great explanation
Thank you for the examples that you used. This is such a good and less scary introduction to time complexity analysis
By far the best explanation I have encountered!
nice
Boyyy YOU GOING CRAZY. Great Explanation!
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/
salamuch homie
Thank you so much for such a clear explanation :)
sure
thank you!
you are the GOAT
I really love your videos. Thanks so much for clarifying so many black knowledge holes 🕳 for me!
love the energy !
Thanks, you explain very clear.
sure!
I was having a problem with understanding what "asymptotic" really mean and you helped me ..thank you very much
This is mind blowing how you explained it. Keep it up. I subed asap.
Bro thanks
Thanks 🙏🙏
A very humongous thanks to you 🙌
yw
U r champ
Good video
Thanks!
For your 100k milestone
Ye
bro ur better than 99% of the online educators and even some professors!
Subscribing is a MUST!
thanks haha
Always a pleasure to watch your video 😇.
cool
Excellent ! I haven't come across such a fantastic explanation so far !
Good explanation
Thanks
sure
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!!
damn that was good. thanks.
sure
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
Your channel is a lifesaver for self-taught programmers...
Thank You!!
Do check out backtobackswe.com/platform/content
a really great job
thx
Helpful!
Thanks
sure
Thank you!
sure
Wow!!
yes
I liked the video, but it was not too clear. You can do it better
ok haha
Do some examples!!!
ok
Be kind, man!
Amazing
thanks
Thanku......
thank u
I really appreciate this explanation because you made a point to explain why asymptotic complexity is important
Great explanation!