Why The Logarithm Is So Important For Algorithms & Data Structures

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!

[@juliansteden2980]

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)

[@lalitac]

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.

[@clem]

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!

[@masternobody1896]

@@clem I want to get a job at google faster than the speed of light

[@masternobody1896]

@@clem thanks for the inspiration

[@masternobody1896]

@@clem never ever give up - elon musk. i want to like elon musk and I want to be like you also

[@galdamez3]

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.

[@KKkaptan]

Conceptually, think about logarithm base (b) of x as the number of times you need to divide x by b until the answer is

[@harispapadopoulos4295]

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

[@sportsgamingcubing1860]

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!

[@peterelst]

weird edit of the opening but useful topic

[@whatinthebloodyhell]

😂

[@clem]

😂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 😛

[@avijitpaul4443]

@@clem 😂😂😂

[@milkymoo16472]

@@clem Nah mate you got me hooked and made me watch it!

[@jakariasami]

This video was amazing! Would LOVE to watch more videos where you explain these types of things. I really mean it.

[@clem]

I really appreciate it! I'll see if there are other topics I can try to simplify like this one!

[@rajvis16]

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.

[@farhadpagdiwala1789]

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.

[@irinagr]

Thanks for pointing the importance of logarithms! Awesome, short and spot on explaination!

[@frushlife]

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

[@Earth-Worm-Tim]

Outstanding! I have always found this to be a rather complex topic to really grasp.

[@z4ar]

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!!

[@jaagviveluguleti4271]

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.

[@kayra4080]

Thank you so much! This made my newly starting informatics journey much more easier, keep up the great work!

[@Jared-Cruz]

You explained this in a way that a non-software engineer or even math savvy person could understand. Fantastic job!

[@eloka9015]

i'm literally a law student and i got it!

[@maxxpellowski2916]

Brilliant explanation, sir. NOW I understand how important they are. Thanks for opening my eyes, yet again.

[@AleX_028]

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*

[@BhupendraSingh-dl5lj]

The best explanation I have seen on the Internet. Perfect

[@mettanotation]

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.

[@sergpodolnii3962]

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.

[@Leshpngo]

This was so cool, it felt like I was grabbing the power lines of cs. Thanks Clement this was a amazing video.

[@charlesopuoro5295]

I absolutely found it insightful. Thanks so much for this.

[@amixengineer]

great video, great explanation, I smashed the subscribe button just to look forward seeing these types of videos. well done and thanks Clément.

[@thecodingfeast]

It took me 24 years to realise what lag(x) is, thanks to clem!

[@sathwicsardana9690]

Awesome explanation -- simplified, distilled and de-mystified

[@suvammondal7053]

Beautifully explained, loved it.

[@Eww...NotTheHumansAgain]

A very useful explanation. Thank you!

[@somnathpaul3004]

Superb explanation. It was never that much easy to me before this video.

[@KaleemKhan-dr4vi]

This is the most amazing explanation I have seen.

[@MagedMegz95]

Amazing. Just amazingly and simply explained. Thanks.

[@KrishnaKaliyuga]

Awesome Explanation Thank You

[@heyheyhey0220]

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.

[@mreagantn]

Great explanation. Thank you!

[@godsdarkestangel4519]

Informative. Thanks Clément.

[@malanbandara]

Wow Clement you're really good at teaching. Thank you

[@brandonblackwell1216]

Best explanation I have ever heard. You are one of a kind sir.

[@siphokazimanana7677]

Well done!!!! Very thoughtful way to explain it

[@sp3ctrums264]

Thank you! Explanation was so helpful

[@AccessCode101]

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.

[@olga8687]

The best explanation of logarithm I've ever heard.

[@pratyushsrivastava4476]

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

[@seandougan8593]

This was good, very to the point on why they are important

[@rachanasingh9476]

awesome video @Clément Mihailescu

[@ursawarior4ever]

algorithms aside, i can tell youve been working out. Good stuff man.

[@vishaldhavale5234]

Really great explanation..Thanks

[@lethatsinkin]

This was super helpful!

[@BJTangerine]

Very nicely explained, even a layman like me was engaged with your content

[@alambez]

Thanks for the insights.

[@kjanshair]

Brilliant Explanation.

[@mariadmt8569]

Mulțumesc pentru explicații!

[@tttmsu]

Super helpful, thank you

[@temiyeakinyemi6236]

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).

[@wian7284]

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

[@EwertonSilveiraAuckland]

Tks for the explanation 🎊

[@Nikolai41Volkoff]

dude, you're the man. thank you.

[@kell7689]

Great explanation!

[@vigneshravichandran2965]

great explanation , now I have realized how the time coplexity is O(log n )

[@mauroquinteros8783]

More visual would be excellent, thanks Clement!

[@quantumleap9520]

Great Explanation

[@danielcardona5268]

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“

[@aperture0]

Nice. I just learnt it using 7 rule.

[@T-The-K]

This helped ty!

[@list9016]

wow- i had no idea i was missing out on something this opowerful

[@TutorialTechie]

I understand every bit he siad great explanation.

[@luiscesar5450]

This was good. Thanks

[@kevinz1991]

Such an awesome video thank you 🙂

[@marvet9573]

Glad I subbed, logarithms actually mean something now other than a pain in the ass on my math exams lol

[@1991hemanth]

Amazing explanation. 🔥🔥🔥

[@srivishnu8983]

interestingly explained !!

[@codecontent9717]

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.

[@Vino359]

Thanks Clement

[@ramseykarr6870]

Wonderful explanation 🙂

[@danielkakai2877]

Great explanation

[@sameerplaynicals8790]

great explanation of log

[@Jonathan-kx2be]

great video helped a lot

[@Djangoo-uy1nl]

Damn it Mr. Jeffreys this is how you explain stuff to students! Great explanation

[@thecashewtrader3328]

yes

[@billykotsos4642]

Thanks, really helpful

[@jibin7277]

very useful man !

[@fatimalmasri7715]

Omg i cant believe it u explain math in the best way ever i swear ure awesome

[@ranjitbisai9335]

very good explanation

[@anshukmishra4520]

Very Helpful video

[@kyeiiih4422]

Just a dope explanation

[@criptik5208]

How do you study after tuning light off, domt you form algos in pen and paper

[@konstantindevelops131]

Understood better than from reading your LinkedIn Post hah Cheers for that!

[@asyrafsyahla7868]

very useful video to Understand

[@techienomadiso8970]

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

[@eric000]

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.

[@lincolnkroll]

Thank you!

[@bhargavpandya9189]

Do more technical videos like these please

[@Dr_Doofenshmirts]

Question, is it possible to make an ad blocker from scratch?

[@rhen4610]

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

[@pablon3115]

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?

[@mishadaro9759]

at last, I understand. Some articles complicate this so much...

[@Why_I_am_a_theist]

New ad of SystemExpert

[@alex-ie7pt]

Can you do a video on Group Theory?

[@nikenuke]

Thanks!

[@TonyBrackins-kt6ie]

Wow. Really good.

[@anshukmishra4520]

KZbin should promote this kind of video

[@_Anna_Nass_]

Unrelated but you have some fantastic bone structure, dude.

[@oltialex]

"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?

[@FahmiEshaq]

man! excellent content

[@tomeyan3544]

thank u so much