Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science
Вставка
- Опубліковано 5 жов 2024
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Logarithms and logarithmic time complexities used to confuse me for a very long time since it was one of those scary things in math where you see a symbol and then you get scared that it is something complex.
Logarithms are very simple. At the most fundamental level, the logarithm asks us a question.
log(8) with a base of 2 asks me: "what do I need to power 2 by to get 8? The answer is 3. 2^3 = 8
log(100) with a base of 10 asks me: "what do I need to power 10 by to get 100? The answer is 2. 10^2 = 100
This generalizes us to understand that a log asks us...what do I need to power my base by to get the number we are taking a log against?
That is what the logarithmic expression evaluates to.
Also, if we have 8 and a log base of 2, we can halve 8 3 times. 8 - 4 - 2 - 1 before we get to a 1 and we cannot cut in half anymore.
In standard mathematics, it is assumed that the base is a base of 10.
In computer science, the base is almost always 2. We will see why.
Where We See Logs In Computer Science:
Levels In A Binary Tree
In general, a binary tree with n nodes will have at least 1 + floor(log_2(n)) levels
When we do something like a tree traversal or heap insertion or removal this is why we use a bound of O(h) which for a balanced binary tree really means O(log(n)).
We will traverse at most a log amoung of levels in the asymptotic sense since that is our tail behavior. Our asymptotic behavior is logarithmic.
Merge Sort & Quicksort
In mergesort, we can only cut the input in half up to log(n) times.
Same for quicksort.
Each sorting algorithm will have log(n) levels of work roughly and then the question becomes what amount of work do we do in each of those levels.
Binary Search
In a binary search, we cut our search space in half every operation based on some predefined searching criteria we define for narrowing search space.
We can only cut our search space in half up to log(n) times.
The logarithm is critical for all of these applications since the question it asks is exactly what we are interested in.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Table of Contents:
Logarithms Matter 0:01 - 0:44
The Fundamental Question We Are Asking 0:44 - 3:34
The Logarithm: Minimum Levels In A Binary Tree 3:34 - 4:52
The Logarithm: Merge Sort Levels 4:52 - 7:09
The Logarithm: Binary Search 7:09 - 9:07
Summarizing Why A Logarithm Is Important 9:07 - 9:46
Wrap Up 9:46 - 10:05
Sort of Mistake At 9:39 -> It can mean many more things hence my * I added. It can be insertion into a binary heap (where we bubble an element up or down doing log() work), it can mean binary search, it can mean splitting of input for sorting, etc. etc. Had to clarify and not assume people knew what I meant.
If you know what a logarithm means then you don't need to memorize some rules (some you will need to know if you are doing calculus). The rules come from the logic and questions that we are asking.
Hello,
Thank you for uploading valuable videos. I have one query. I have just started EPI. how long did you take to complete the entire book for first time? If you follow any strategy ,can you please let me know it?Is there any way to contact you through email?
@@MrKishorebitta about a week or so
@@BackToBackSWE about a week? looks like u spent more than 12 hrs per day on that book.
@@MrKishorebitta :)
Man this video is worth 68 college slides about time complexity
This is without a doubt the best and clearest explanation I've ever seen!
hey, oh...check out my new mergesort video. Just put it out. I think it hammers the point home.
@@BackToBackSWE Awesome !! The best video on 0{logn)
@@adarshsharmanit356 thx
Definitely the best
Kind of blown away at how amazing this was explained.
This is by far the clearest explanation of log(n). The clouds just parted, I'm basking in that divine light of knowledge. Thank you.
may you flourish
AAAAAAAAAAAAAAAAAAAAaaaaaaaaaaaaaaaaaaaAAAAAAAAA(divine music plays)
Im feeling that euphoria right now
Holy shit me too
My math teacher couldn't teach me in 5 years what you managed to explain in a 10min video, you da man!!
LOL, same brother utube teachers are genius
I have a math degree and never thought of it as cutting into parts, great insight and very helpful!
I attend a top 25 university and the CS professors here are unable to explain this material as succinctly and easily as you. Many thanks!
Happy Halloween 🎃 Thank you for your kind words, philipskeen! You get 25*2 treats - 50% Off our exclusive lifetime membership use the code SPOOKY50 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SPOOKY50
Thinking of a base 2 log as "how many times can I divide a number by 2 until I get to 1" makes so much more intuitive sense than how I used to think of it "to what power can I raise 2 in order to get this number."
Yeah Think of 2 as halving, think of 3 as thirding, think of 4 as fourthing, think of 10 as tenthing...and so on.
2 minutes in and my mind is blown. I knew there was something about Log(n) that was being held a secret!! This explanation--wow I actually have no words. THANK YOU!!!!!!
sure haha
My prof tried explaining this last class, and literally every student was so confused on it. Im so glad i found this video. thank you so much
ye, welcome
This explanation has finally got rid of the confusion i always ended up having while writing down the time complexity. I cannot thank you enough man. This video is a game changer for me. Thanks a lot.
nice
This was the loveliest explanation, I’m just a freshman trying to do good on the AP CS test in high school
Nice. Hey, my advice to you (what I'd tell myself). Get very good at programming. High school will likely come easy to you. Screw all the rest...just try to get straight A's and grasp all subjects (especially math). It only gets harder in college.
Try getting into the best college you can humanly get into. Don't stress too hard since state schools are still huge and awesome, but it definitely helps when a name is behind you during applications for job, etc.
BUT...focus on this...get good...great...at programming and using your brain to come up with solutions.
That's all. Stay fit...hit the gym...and BE A SOCIAL HUMAN. It is hard for most CS majors but make your best efforts to have as many friends & meaningful relationships in your life as possible.
We are humans with feelings and emotions...not robots...this is something I didn't understand until about 2 years ago.
But yeah...find your programming niche...try all the stuff (web, backend, frontend, etc.) and find what holds your interest.
And...yeah...that is my advice. These Leetcode problems are kind of detached from reality but are crucial to get a job at a big SWE company at the time of this comment's writing. Just brush up on these as well but..yeah.
Get good as shit at programming and build stuff for fun.
Then when you really need to step up to the plate when you are in college you have the skills to start anything around...AND all the people around you will be smart too so...yeah...cool stuff can happen.
Ok, rant over. I could say more but I need to achieve more to say it so I'm not just blowing hot air.
@@BackToBackSWE wish someone had told me this when i was in highschool.
@@hacker-7214 yo
@@BackToBackSWE right now im a sophomore majoring in cs. At a top 50 cs school US (because i didnt try hard in hs, bad grades low test scores). Anyways your videos are helping me a lot. Im starting to learn data structures even tho im late to the party (i have only been coding for the past year, started coding freshman year in college). I am working hard to get an intership.
@@hacker-7214 nice, hey
You just explained something my professors have struggled to for years in 10 minutes. Thanks a ton!
sure!
This has to be one of the most helpful, easy to understand, and most significant CS/CE tutorials I've ever watched. Thank You! Wow, it took me 4 years to come across this video. God Bless You Sir!
I wish you were around during my undergrad, you always provide the cleanest examples to complex CS subjects. Keep doing your thing bro!
yup
I love that instead of focusing on code you focused on the concept.
this is all my concepts of algorithms have been wanting for so long.Thankyou for telling us more than "log is reverse of exponentiation"
sure.
we did this way back in junior school mathematics in Nigeria. I never knew it would turn out to be an issue for grown ups. My love for coding brought me here. Thank you
great
The fact that it's always base 2 implied cleared up a lot for me. Excellent video, thank you!
Sure
Amazing explanation! Just finished a lecture Involving sorting algorithms and couldent piece together where O(Log n) and O(n Log n) came from. After watching everything just comes together! Thank you so much!
nice
dude i dunno how you're not blowing up.. you're literally the best teacher i've seen on youtube. thanks man!
thanks and things take time. I'm patient.
This is the video that I always wanted but didn't know how to search for.
4 years , from 4 years it was hunting me today i got my answer , thanks a lot man thanks a tons .
ye
You're a really good teacher. Thank you for breaking this down so simply! Please make more content :)
ok
This is the only channel you need to watch to learn Complexity analysis. Nice work!!
thanks
From the deep down from my heart I thank you for eternity..
May the internet flourish.
Finally, it feels good when you understand it. thanks
sure
Duuuuude, you just helped me pass my exams! I am forever grateful!
U a beast
trust me, you explain things much better than my Professor. Keep up the good work bro!!
The validation matters the most!
This is a fantastic explanation and display of applications of logarithms in computer science. Thank you for taking the time to make this!
sure
Finally! Extremely lucid explanation man! Loved it
Thanks a ton!
great.
Like your video! You even make some business student such as me feels like learning computer science is such a fun thing.
haha nice, do it!
This is the best explanation I've ever seen. Thank you so much :)
Thank you, Sir! Fantastic explanation!
sure
This is definitely the best channel I've come across for Data Structures and Algorithms. The videos are especially comprehensive and everything is explained in depth before moving to the next segment. Great work.
Thanks
wow! Finally, someone speaking English when explaining big0 time complexities! No Joke! Thank you!
hey
It’s actually convenient when there is not a language barrier.
Was struggling to understand the conceptual aspect of logs in my algorithms class, this video helped so much. THANK YOU!!
You just compacted two weeks of studying into 10 minutes, thank you
great
This dude is insane with how clear and concise his explanation is. I was skeptical clicking on a 10 min video hoping to understand Logs but I can learn a thing or two about teaching from this.
Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
It is indeed very clear explanation and on point. Thanks a lot! it really helped me
sure
dude you clearly have a talent to teach complex things in a simple to understand way. Great job 👍
I have maths backgroud even then i can't understand but
Now I finally understand
nice
I've been developer for a few years now and wanted to get a refresher. You broke this down and gave some really good ways of remembering things. Thanks!
this is the best thing that happened to me
hahaha
Man, this is the clearest explanation about log(n) i've ever seem. Thank you so much
The explanation was just excellent bro
Thank you so much
sure
buddy, ur channel, honestly , is the best channel for IT peopel... great thanks from the bottom of my heart !
This is the best explaination I ever saw 😍💖🙏
thanks
After 3 years of professional software development I finally really understand it, much love!
great
you're a legend mate!! thank you!
hey
You are a tremendously talented teacher! I cannot believe I understood this integral concept in a mere 10 minutes
nice
You're amazing, thanks!!!
ye
Within a minute or so, I knew this was going to be one of the best explanations I have seen or read. Thanks!
I've been reading Grokking Algorithms 2nd Edition, and found your explanation better. Though, I love the book too."
One thing that bothers me in most explanations, including in GA2ndEd, is that they rarely deal with the case where the item you are looking for is the last one.
In your example, of 1, 2, 3, 4, 5, 6, 7, 8 if we are looking for "8", and using the floor division approach (which GA2ndEd uses) we start with index 3, too low. Next we look at "5" within 5, 6, 7, 8. 2nd attempt, too low. Next we look at 7 within 7,8. Third attempt, and still too low. Now, unless we know ahead of time that the item we're looking for is guaranteed to be in the set, then we must make a 4th comparison to verify that 8 is indeed the last available item to examine.
The book says it is going to explain this in chapter 4 (I'm only on 3) as to why constants are not used in Big O notation, but I just wish they and others would note this nuance when the list of items is a power of 2.
I almost never comment but this was an awesome video. Exactly what I was searching for
Nice! If you liked this we have a active class running now, I'd love you to join if interested
I’ve been searching everywhere for a clear explanation and here it is. Well done. Thank you so much.
no doubt, just one word, AWESOME :)
thanks
You have no idea how happy I am to have come across your channel. This has helped me so so much. Please keep up the good work.
nice, thanks
This is amazing omg ❤❤
hey
This has got to be the best explanation. This explains the time complexity of merge sort and quick sort as well. Thanks a lot!!!
thanks
Difference with nlogn and logn???
what
Crystal clear explanation. It's also great that you cut out parts while you write on the board. Most others don't do that! Thank you!
thanks
I searched so many videos for Big O and understood everything except logs.. Thanks much. This is the best explanation ever.
thank you. this was my doubt for a long time. not many ppl have such good understanding of logs.
Keep hustling!
Dude, this explanation was as CLEAR AS WATER... After many years in the Comp Scie world, I finally truly understand logarithmic complexities
Thank you for making me understand something countless teachers and tutors failed to do.
Happy to help!
This is the first time I have understood what logs are. Thank you so much. This is the best explanation I've ever seen. Keep it up
the way this man speaks and explains is exceptionally clear.
I can't believe I finally got it. Thank you so much.
sure
Such a clear explanation! I was able to come to the conclusion before the end of the video.
Amazing! Subscribe to our DSA course with a flat 30% discount for more explanations and content b2bswe.co/3HhvIlV
Thanks,I never got this concept, but you made it very simply and clear.
great
DUDE! This helped me so much!! Beginner coders of the internet appreciate you my dude!
was searching for this my entire semesters! Finally got it out in 10 minutes. Kudos!
This is the best video to explain nlogn and logn time complexity.i was confused for over a year.
Love it. Great explanation. Clear and concise. Thank you
sure
Watched an hour lecture and couldn't understand a thing. Watched 10 min of this video and is now all clear. Thank you
sure
How can someone not appreciate this man. His videos are BY FAR, the best CS videos I have seen ever. Great stuff, keep it up!
This explanation is pure art, super simple short and efficient yet effective explanation. Love you man and keep up the good work.
omg, I finally understand the general concept of this tern, many thanks to you
great to hear!
this is unbelievable.. literally the best video I've ever seen
Haha glad you liked it!
Thank you for this video. It will helps to understand the concept of logarithms in computer science.
sure
Beautiful! Finally, after all these years i understand this!
Ive watched like 7 videos on this topic and yours was the first that made sense thank you!
Thank you! Please enjoy a special code from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=slxthkween 🎉
Omg! The perfect explanation. It's clear, simple, and understandable
Needed this, patience - > this channel will go places!
PS : Been trying to understand what is going on with this logarithm bullshit ever since high school. Now it's not bullshit anymore
thanks
@@sanjeevsiva17 yeah, same
I was very terrible at cracking the time complexity when it comes to logn but you made it just a 10min thing...Thanks tonnes
This happens when someone who truly understands the topic shares his knowledge and knows how to do it. In a school log n is just another function to solve. This kind of practical explanation is the best! Without It there is no way to use your imagination to think about logarithms! Thanks!
Bro please do more videos. Absolutely amazing, the amount of clarification you are giving is 👌👌
sure
This exaplanation is awesome, wonderful. Thank for the wonderful service!!
one of the best explanation i ever heard regarding why do we have logarithmic time complexity......Great Explanation...Thanks
Amazing video! You did an amazing job keeping us engaged and simplifying things.
Awesome video - thank you ! You just explained in 9 minutes what it took me a full class and two hours of reading to understand.
Thank you for the very clear explanation. You saved my allot of time :)
sure
I finally understand logarithms in time complexity!! Intuitive explanations like this are so helpful!
I've genuinely struggled horribly with this aspect of Big O notation because I couldn't just wing it, but now I really understand this. Thanks!
You helped me solve a lot of questions I had for so long. Simple and crisp !! Thank you !!
Thank you, glad you liked it 😀
Do check out backtobackswe.com/platform/content
and please recommend us to your family and friends 😀
I have struggled with math, and always was behind when it came to Computer Science things directly related to mathematics. My mind is fucking blown dude. It all makes sense, whenever I looked at Logs my eyes would glaze over and I'd struggle. You've cleared everything up for me, thank you.
Awesome job, you told me everything I needed to know in the first 3 minutes.
nice
This guy is just incredibly good at explaining difficult things.
Never in all my life have I ever heard anyone explain this so perfectly.
Thank you 🎉 Please enjoy a special coupon from us - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=SUB 🚀
subbed, best video ive seen on understading logs
welcome and thx
This is the best channel man!!!!
I seldom come across channels like these!
this guy explains everything which is awesome!