Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science
HTML-код
- Опубликовано: 29 янв 2019
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
📹 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 
Наука
![The Most Useful Curve in Mathematics [Logarithms]](http://i.ytimg.com/vi/OjIwCOevUew/mqdefault.jpg)
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 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
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.
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
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
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
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!
You're a really good teacher. Thank you for breaking this down so simply! Please make more content :)
ok
I wish you were around during my undergrad, you always provide the cleanest examples to complex CS subjects. Keep doing your thing bro!
yup
Amazing video! You did an amazing job keeping us engaged and simplifying things.
Thank you so much! I've been stuck on this for an extremely long time! This has to be the best and clearest explanation i've ever seen!
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
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'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!
I’ve been searching everywhere for a clear explanation and here it is. Well done. Thank you so much.
You just explained something my professors have struggled to for years in 10 minutes. Thanks a ton!
sure!
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.
was searching for this my entire semesters! Finally got it out in 10 minutes. Kudos!
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!
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!
It is indeed very clear explanation and on point. Thanks a lot! it really helped me
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
Awesome job, you told me everything I needed to know in the first 3 minutes.
nice
This is the video that I always wanted but didn't know how to search for.
Thank you, Sir! Fantastic explanation!
sure
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
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 🎉
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.
The explanation was just excellent bro
Thank you so much
sure
This is such an amazing explanation! I finally understand how this works. Thank you!
great and sure
Awesome video - thank you ! You just explained in 9 minutes what it took me a full class and two hours of reading to understand.
From the deep down from my heart I thank you for eternity..
May the internet flourish.
you're a legend mate!! thank you!
hey
This is the best channel man!!!!
I seldom come across channels like these!
this guy explains everything which is awesome!
Thanks for this, mate! Logarithms used to be my only Math Nemesis in highschool and now they came back to haunt me in my Algorithms course. It all makes sense now 🙏
Duuuuude, you just helped me pass my exams! I am forever grateful!
U a beast
this is the best thing that happened to me
hahaha
omg, I finally understand the general concept of this tern, many thanks to you
great to hear!
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
You're amazing, thanks!!!
ye
I have maths backgroud even then i can't understand but
Now I finally understand
nice
Finally! Extremely lucid explanation man! Loved it
Thanks a ton!
great.
I love that instead of focusing on code you focused on the concept.
This is amazing omg ❤❤
hey
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
Thank you for putting so much energy and efforts in this video! This was definitely the most intuitive way to learn log(n). And especially those were the golden words when you referred to how to think when a solution is asked in log(n) ❤
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.
no doubt, just one word, AWESOME :)
thanks
You just compacted two weeks of studying into 10 minutes, thank you
great
Love it. Great explanation. Clear and concise. Thank you
sure
This is the best explanation I've ever seen. Thank you so much :)
This is the best explaination I ever saw 😍💖🙏
thanks
Difference with nlogn and logn???
what
"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.
Incredible explanation, going to look through the rest for my interview prep. Thank you dearly
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
Thank you for explaining log n in the best possible way with the minimum amount of time required!! You're a legend. Subscribed! Keep up the good work!
Seriously this is a GREAT job of explaining this rather difficult subject matter. Absolutely spot on wonderful! Thank you so much!
This is the only channel you need to watch to learn Complexity analysis. Nice work!!
thanks
subbed, best video ive seen on understading logs
welcome and thx
The fact that it's always base 2 implied cleared up a lot for me. Excellent video, thank you!
Sure
Dude, this explanation was as CLEAR AS WATER... After many years in the Comp Scie world, I finally truly understand logarithmic complexities
Thanks for this amazing explanation. Before watching this I was super confused on how to calculate O(log n) and now I have a better understanding!
great
This is so awesome! You are at another level making it so easy to understand! Many thanks!
sure
You are a tremendously talented teacher! I cannot believe I understood this integral concept in a mere 10 minutes
nice
Many Thanks , trying to learn about Programming and when it came to searches on an intro level , Logarithm came up and you have aptly explained it in the context of Computer Programming .
great
Was struggling to understand the conceptual aspect of logs in my algorithms class, this video helped so much. THANK YOU!!
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 finally understand logarithms in time complexity!! Intuitive explanations like this are so helpful!
What a simple and very clear explanation of logn. Thanks you so much!
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!
Bro please do more videos. Absolutely amazing, the amount of clarification you are giving is 👌👌
sure
by far one of the best educational videos. I really needed to try to understand this and you made it easy. thank you
I wish I would have come across your channel earlier this year. Thanks for producing quality content and keep up the good work.
Thank you , The Explanation that I was looking for :)
great
Now I understand log(n) complexity. Thanks a lot! It was great.
Super intuitive explanation. Thank you for creating this!
thank you for watching :)
Definitely the absolute best explanation, you made it so clear and simple a toddler could understand it!! Thank you very much!
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 😀
Wonderful natural teaching style. Revealing some key intuitions for logarithms in CS. Thank you.
4 years , from 4 years it was hunting me today i got my answer , thanks a lot man thanks a tons .
ye
Wow. Perfect. I struggled with other explanations but this was very clear!
Fantastic, it's straight to the point. I am forever grateful!
sure
Thank you for this video, this greatly helped. Superb content!
great.
buddy, ur channel, honestly , is the best channel for IT peopel... great thanks from the bottom of my heart !
thank you. this was my doubt for a long time. not many ppl have such good understanding of logs.
Keep hustling!
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!
That was really great video, thank you so much!
sure
so cool and clear explanation. thanks!
Hats off, for explaining the mystery topic in a simple word "Halving"!! The best contribution on the RUclips!
ye
This is gold and needs to be required for studying Big O. Well done 🤙
thx
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
This is AMAZING thank you so much I finally understand!
sure
SO AWESOME!!!... thanks for bringing back the basics to help us understand the complexity clearer. Thank you so much. liked-subscribed