Why The Logarithm Is So Important For Algorithms & Data Structures
ฝัง
- เผยแพร่เมื่อ 16 มิ.ย. 2024
- This is why the logarithm is so important for algorithms, data structures, big o notation, and general software engineering.
AlgoExpert: www.algoexpert.io/clem
SystemsExpert: www.systemsexpert.io/clem
MLExpert: www.algoexpert.io/ml
My LinkedIn: / clementmihailescu
My Twitter: / clemmihai
My Instagram: / clement_mihailescu
Prepping for coding interviews or systems design interviews? Practice with hundreds of video explanations of popular interview questions and a full-fledged coding workspace on AlgoExpert - www.algoexpert.io - and use the promo code "clem" for a discount on the platform! - วิทยาศาสตร์และเทคโนโลยี
Very good video but the math in your example is wrong ;)
4 billion nanoseconds are 4 seconds (1 billion = 1e9; 1 ns = 1e-9s).
Nevertheless the logarithmic calculation is 134,217,728 x faster (2^32 / 32)
Correct. But how fast the algorithm with logarithmic time complexity is, as compared to algorithm with linear time complexity, depends. For 4 Billion elementary operations, linear one takes 4E9 nanoseconds while the logarithmic one takes 32 nanoseconds. So, in this case the algorithm with logarithmic time complexity is 4E9/32 i.e. 125,000,000x [125 Million times] faster.
Argh! This is why you get someone to review your code (or video, in this case 😛) Yes, of course, 1ns = 10^(-9)s, so 4 billion nanos is 4s. I too quickly trusted what I saw on Google by typing "4 billion nanoseconds in days," which deceived my eyes. The analogy still certainly stands, because the logarithmic algorithm is a whopping 125 million times faster than its linear counterpart, but thank you for the correction!
@@clem I want to get a job at google faster than the speed of light
@@clem thanks for the inspiration
@@clem never ever give up - elon musk. i want to like elon musk and I want to be like you also
I always had a hard time explaining logarithmic time because I didn’t understand the math. Problem solved. This is one of the best explainer videos I’ve seen in a while.
Conceptually, think about logarithm base (b) of x as the number of times you need to divide x by b until the answer is
Hell yeah. I love getting stuff explained to me by clement. I still remember the logarithm video from algoexpert but getting a refresher was nice
weird edit of the opening but useful topic
😂
😂I wanted to tempt users into watching the full video with an arguably intriguing glimpse at a clip from later on in the video, but perhaps the edit wasn't that great 😛
@@clem 😂😂😂
@@clem Nah mate you got me hooked and made me watch it!
Fantastic timing! I am working on a crazy 2 week assignment for a college course at the moment and it has a bunch of runtime complexity problems so this is super useful for me!
You watch so many videos but there are very few videos that make you feel wiser after watching them. This is truly one of them. The way you explained, I hope the professor in the colleges. are able to explain is such a simple way.
This video was amazing! Would LOVE to watch more videos where you explain these types of things. I really mean it.
I really appreciate it! I'll see if there are other topics I can try to simplify like this one!
Excellent video Clement. Thoroughly enjoyed watching this for refreshing and jogging my memory on why binary search and trees are so important in Algos and DS.
Thanks for pointing the importance of logarithms! Awesome, short and spot on explaination!
Clem thank you so much - I've watched countless videos over the last few days trying to wrap my head around Big O and this was my lightbulb moment - Software dev with 5 odd years professional experience with zero math / algorithms background who has ignored this stuff forever
Outstanding! I have always found this to be a rather complex topic to really grasp.
Thank you so much! This made my newly starting informatics journey much more easier, keep up the great work!
Can't believe I sat through all of this completley focused and invested lol. Starting my compsci study this fall and this was very insightful. Thanks!!
Most valuable video I have received today and exactly what I was looking for....yesterday I watched your How to learn faster video and there you were stating the importance of logarithms...so I was looking for the free video of yours but couldn't find it in your website....now that you've mentioned it.....what a timing!!!! My manifestation always works.
Brilliant explanation, sir. NOW I understand how important they are. Thanks for opening my eyes, yet again.
The best explanation I have seen on the Internet. Perfect
great video, great explanation, I smashed the subscribe button just to look forward seeing these types of videos. well done and thanks Clément.
As a person with STEM background I should say that under normal log or ln we usually imply reverse to e^x operation (in electronics engineering convention for log - reverse to 10^x for multitude of dB units). Exponents and ln operations go hand in hand when you deal with calculus more or less on regular basis. And this guy is Log2, what can be a point of confusion.
This was so cool, it felt like I was grabbing the power lines of cs. Thanks Clement this was a amazing video.
I absolutely found it insightful. Thanks so much for this.
You explained this in a way that a non-software engineer or even math savvy person could understand. Fantastic job!
i'm literally a law student and i got it!
Sir what an explanation...I never thought logarithms in such perspective and thank you much for that this knowledge I won't forget for my entire life .
*Hands down*
Beautifully explained, loved it.
Awesome explanation -- simplified, distilled and de-mystified
This is the most amazing explanation I have seen.
Great video 👍🏼. Big-O assumes fundamental operations are the same speed, but it’s useful to know IRL they are different and that can make a huge difference. Famously, John Carmack when developing Quake had to optimize the inverse square root operation as part of the algorithms that made the game playable. I was a game dev before I got my CS degree and it always seemed a little odd detailed optimization wasn’t taught. Oh well theory vs practice I guess.
Hey Clement, great stuff with something like this :)
also on a slightly different note I felt some energy shift in your overall personality outlook from the video..kinda like did you changed a bit in anyway or with something that's going on lately? :p
Amazing. Just amazingly and simply explained. Thanks.
A very useful explanation. Thank you!
Superb explanation. It was never that much easy to me before this video.
Well done!!!! Very thoughtful way to explain it
Wow
Clement you're really good at teaching. Thank you
Best explanation I have ever heard. You are one of a kind sir.
Awesome Explanation
Thank You
Great explanation. Thank you!
Informative. Thanks Clément.
Thank you! Explanation was so helpful
This was good, very to the point on why they are important
It took me 24 years to realise what lag(x) is, thanks to clem!
The best explanation of logarithm I've ever heard.
Wow man, you should do more videos about math. I know that's your major but imagine how many people are looking to learn algebra and linear algebra or whatever type of algebra that can help them better understand algorithms.
My college didn't prepare me for Time Complexity so I just ran over DSA like it was a normal subject. This really opened my eyes, Time to Learn again
Very nicely explained, even a layman like me was engaged with your content
Really great explanation..Thanks
This was super helpful!
algorithms aside, i can tell youve been working out. Good stuff man.
Brilliant Explanation.
In algorithms we say O(log(n)) because all log bases are the same O set. They differ only by a constant coefficient and therefore are the same O.
awesome video @Clément Mihailescu
I completely understood this video because I just started learning what Big O notation is... Now I can see why O(log n) is better than O(n).
Great explanation!
great explanation , now I have realized how the time coplexity is O(log n )
More visual would be excellent, thanks Clement!
wow- i had no idea i was missing out on something this opowerful
Mulțumesc pentru explicații!
Thanks for the insights.
Super helpful, thank you
Tks for the explanation 🎊
Great Explanation
dude, you're the man. thank you.
I understand every bit he siad great explanation.
Such an awesome video thank you 🙂
Wonderful explanation 🙂
Amazing explanation. 🔥🔥🔥
Glad I subbed, logarithms actually mean something now other than a pain in the ass on my math exams lol
This was good. Thanks
"When a measure becomes a target, it ceases to be a good measure." Do you think this fits to the fact that big companies ask for algorithm problems and we blindly try to prepare for them?
interestingly explained !!
great explanation of log
Understood better than from reading your LinkedIn Post hah Cheers for that!
Hey man, please release a course or playlist for colleg dropout trying to learn computer science. One important thing is in what order to learn what and what to learn in parallel. Please consider maths too in it. It would help a lot of souls. Thanks and amazing work. Appreciate it, really.
Great explanation
very useful man !
Thanks Clement
very good explanation
Wow such an interesting realization you've made me have today 💪😃. I never thought of the log this way.
Now that means if our algorithm divides the list into k groups say 3 groups...we could use log to base k which is 3 in this case.
🤦🔥🔥🔥💯💯💯 This is amazing
Thanks, really helpful
Nice video, to me thinking of logarithm is more intuitive if you think of it as the operation that tells you how many times you can successively divide by the base, instead of thing of it as a inverted power. Essentially “how many times can I chop in half“
Nice. I just learnt it using 7 rule.
This helped ty!
great video helped a lot
Omg i cant believe it u explain math in the best way ever i swear ure awesome
Damn it Mr. Jeffreys this is how you explain stuff to students! Great explanation
yes
Do more technical videos like these please
Just a dope explanation
Very Helpful video
very useful video to Understand
I just had one wish, why is youtube not Medium where I can give you 50likes, cause you deserve Everything good in life brother. for this beautiful explanation 💯.
at last, I understand. Some articles complicate this so much...
Unrelated but you have some fantastic bone structure, dude.
TH-cam should promote this kind of video
I greatly appreciate this video but just want to point out one correction that might help people get the correct understanding of the time complexity problem you presented. First of all, 1 nanosecond = E-9 second [here E is the engineering notation] i.e. 1 Billion nanoseconds make 1 second. Now, if the algorithm with linear time complexity performs 4 Billion [4E9] elementary operations, each taking 1 nanosecond, it will take 4 Billion [4E9] nanoseconds i.e. 4 seconds to execute. On the other hand, if the algorithm has logarithmic time complexity, it will take ~32 nanoseconds to execute 4 Billion elementary operations. Now, this is still really remarkable. We just can't imagine and comprehend how quick 32 nanoseconds really are. To put into perspective, in the time required by the algorithm with linear time complexity to execute i.e. 4 seconds, the algorithm with logarithmic time complexity can be executed 125 Million times. Logarithm is so fascinating!
- A high school senior
@Peace Roasted Engineering notation or engineering form is a version of scientific notation in which the exponent of ten must be divisible by three (i.e., they are powers of a thousand, but written as, for example, 10^6 instead of 1000^2). As an alternative to writing powers of 10, SI prefixes can be used, which also usually provide steps of a factor of a thousand.
Source: Wikipedia
@Peace Roasted I think it's fairly common.
Argh! This is why you get someone to review your code (or video, in this case 😛) Yes, you're totally right. I too quickly trusted what I saw on Google by typing "4 billion nanoseconds in days," which deceived my eyes. The analogy still certainly stands, as you very nicely highlighted with your perspective, but thank you for the correction!
@@clem No problem when you've got Peer Reviewers!
@@clem.. no offense.. but why would you have to Google 4 billion nano seconds of you are a software engineer?? I was interested to do your course but now you put doubt in my mind.
I will come back to this few years later after I graduate on my Computer Science college. Philippine College is real slow and basic compare to high standards college like in the US
I'm not sure if logarithmic time complexity requires to operarate in parallel (with concurrency or multithreading) to make sense. In case of adding the numbers of an array of eight elements, in a logarithmic time complexity, once the array is split in three levels, then it will perform each sum in parallel. For instance, for the first operation, at the same time it will perform: 1+2=3; 3+4=7; 5+6=11; 7+8=15. Then for the second operation, also at the same time: 3+7=10; 11+15=26. And for the third operation, also at the same time 10+26=36.
Am I right?
In the real computing world for simplicity O(log n) can be thought of as O(1) when weighted against O(n) and O(nlogn) as O(n) when compared to O(n^2) algorithms etc right? to make things simpler right? for worst case big O scenarios.
man! excellent content
How do you study after tuning light off, domt you form algos in pen and paper
New ad of SystemExpert
Fantastic speaker. I wish I had those skills. To those who corrected Clement for not getting it right about how long 4 billion calculations took: please stop. He made it clear he didn't know or need to know to make his point.
Wow. Really good.
0:02 Did you forget to edit this out?
lol it happens
😂It was meant to make people want to watch the video more! I guess it didn't have the intended effect 😬
@@clem You're always 2 steps ahead of us, checkmate.
Thank you!