Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science
ฝัง
- เผยแพร่เมื่อ 24 ธ.ค. 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
I have a math degree and never thought of it as cutting into parts, great insight and very helpful!
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 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
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
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
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.
I love that instead of focusing on code you focused on the concept.
You just explained something my professors have struggled to for years in 10 minutes. Thanks a ton!
sure!
At last I got the *intuitive* explanation of logarithm which is that it asks a question that can be asked in following ways:
1. How many times can you divide the input no. by the no. in the base so that you reach 1?
2. How many times you need to multiply the base no. so that you get the no. in the parentheses?
Both questions are essential to get a complete picture of logarithms. Without the 1st question, I don't think that anyone can understand sorting and searching algorithms that have logarithmic complexity.
Enlightening explanation. Thanks.
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
YES. This is why profs can't teach most of the time. They're so smart and have understood this on a deep level for so long, that the obvious explanation of how things work just eludes them. This makes so much sense and just gets right to the heart of what is going on. Thank you!
From the deep down from my heart I thank you for eternity..
May the internet flourish.
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.
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.
I don't ever comment on youtube videos. This might be the best video I have ever seen!! Thank you so much for your time and effort into making this video. I subscribed and donated to the fundraiser you're supporting. Wish I could do more, this video was worth gold to me!
Great haha
Thank you, Sir! Fantastic explanation!
sure
"one of those scary things in math where you see a symbol and then you get scared that it is something complex." As I get further and further into my journey with code, I realize that almost everything that seemed really difficult was only that way because I assumed it was too difficult. Every time I stumble with a concept I am shocked at how simple it actually is. This understanding has propelled my learning abilities to new heights as I no longer assume I can't learn something. Thanks so much for this amazing straight to the point video. Subscribing for sure.
This is the video that I always wanted but didn't know how to search for.
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 🚀
You're a really good teacher. Thank you for breaking this down so simply! Please make more content :)
ok
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!
Duuuuude, you just helped me pass my exams! I am forever grateful!
U a beast
This is the only channel you need to watch to learn Complexity analysis. Nice work!!
thanks
This is a fantastic explanation and display of applications of logarithms in computer science. Thank you for taking the time to make this!
sure
I spent last week miserable because I could not understand an explanation of logarithms that I payed money for. This was a much more effective explanation than 'premium' paid content. Well done.
great to hear! What did you buy lol
You just compacted two weeks of studying into 10 minutes, thank you
great
Dude, this explanation was as CLEAR AS WATER... After many years in the Comp Scie world, I finally truly understand logarithmic complexities
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!
4 years , from 4 years it was hunting me today i got my answer , thanks a lot man thanks a tons .
ye
this is the best thing that happened to me
hahaha
I love this video, thank you :)
sure
It is indeed very clear explanation and on point. Thanks a lot! it really helped me
sure
buddy, ur channel, honestly , is the best channel for IT peopel... great thanks from the bottom of my heart !
The explanation was just excellent bro
Thank you so much
sure
This is the best explanation I've ever seen. Thank you so much :)
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!
you're a legend mate!! thank you!
hey
trust me, you explain things much better than my Professor. Keep up the good work bro!!
The validation matters the most!
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
very nicely explained, Thanks
sure
no doubt, just one word, AWESOME :)
thanks
The fact that it's always base 2 implied cleared up a lot for me. Excellent video, thank you!
Sure
You're amazing, thanks!!!
ye
I learn Computer Science & I have a Data Structure exam , you just made my life easier thank you
This is amazing omg ❤❤
hey
My GOD!
SPEECHLESS, HE EXPLAINED IT SO WELL ! From Always getting lost on why Algo vids straight up put logs as complexity to understanding what is actually going on . Makes so much sense rn
Difference with nlogn and logn???
what
Finally! Extremely lucid explanation man! Loved it
Thanks a ton!
great.
This is the best explaination I ever saw 😍💖🙏
thanks
I searched so many videos for Big O and understood everything except logs.. Thanks much. This is the best explanation ever.
the way this man speaks and explains is exceptionally clear.
After 3 years of professional software development I finally really understand it, much love!
great
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
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
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
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!
Fantastic video! 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
I graduated 6 years ago. Even after that I tried to learn DSA for enormous times and failed every time. I didn't understand the logarithmic concept. Suddenly, a few moments ago I came up with the idea to learn it again and found this video. This video explains a lot to me. Thanks a lot.
Glad it helped 😄 We'd love for you to check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
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.
Never thought a 10 min video can clear up so many confusion... by far this is my best 10 minutes investment
Fast, clear explanation! Cheers from a fellow engineer :)
ye
Man, this is the clearest explanation about log(n) i've ever seem. Thank you so much
This explanation is pure art, super simple short and efficient yet effective explanation. Love you man and keep up the good work.
I love you man! You taught me logarithm in a new way. I was always uncomfortable with logarithms, it felt like every time I learned it I forget it very soon. I think the keyword halving and tenthing just lit my light bulbs forever in sha Allah! May Allah reward you for this!
great
dude you clearly have a talent to teach complex things in a simple to understand way. Great job 👍
you deserve a place in heaven. You and all those who are dedicated to sharing some of their wisdom.
thanks and I don't have wisdom, I go to college for Computer Science so I study this full-time.
this is unbelievable.. literally the best video I've ever seen
Haha glad you liked it!
Bro, I'm watching this video at 12am thinking "WHY DIDN'T MY TEACHERS EXPLAIN IT LIKE THIS YEARS AGO" lmao. Excellent video man - you've been blessed with the gift of teaching - continue to share that gift with the world :)
I'm Sold. Best Explanation I've heard so far!
thx
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
Was struggling to understand the conceptual aspect of logs in my algorithms class, this video helped so much. THANK YOU!!
Very nice breakdown. I was doing an Hackerrank challenge that involved sorting and I ended up here while researching logs! Earned my sub!
man!!!.... he explained it like its nothing, best and simplest explanation i have seen sooo far :D
very awesome ....you have easily explained where to use logN time complexity.
one of the best explanation i ever heard regarding why do we have logarithmic time complexity......Great Explanation...Thanks
Thank you so much. It all makes sense now.
sure
DUDE! This helped me so much!! Beginner coders of the internet appreciate you my dude!
This is the best channel man!!!!
I seldom come across channels like these!
this guy explains everything which is awesome!
Finally, it feels good when you understand it. thanks
sure
You are a tremendously talented teacher! I cannot believe I understood this integral concept in a mere 10 minutes
nice
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
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
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 🚀
I’ve been searching everywhere for a clear explanation and here it is. Well done. Thank you so much.
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 🎉
This is by far the best explanation of logarithms in time complexities. 👏
Love it. Great explanation. Clear and concise. Thank you
sure
Hats off, for explaining the mystery topic in a simple word "Halving"!! The best contribution on the TH-cam!
ye
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