Deeply Understanding Logarithms In Time Complexities & Their Role In Computer Science
ฝัง
- เผยแพร่เมื่อ 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 - วิทยาศาสตร์และเทคโนโลยี
![[TH] VCT Masters Shanghai Playoffs DAY 5 // 100T vs PRX | FUT vs TH](http://i.ytimg.com/vi/q75pv359eP4/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 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!
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 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!
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
I’ve been searching everywhere for a clear explanation and here it is. Well done. Thank you so much.
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 wish you were around during my undergrad, you always provide the cleanest examples to complex CS subjects. Keep doing your thing bro!
yup
This is the best channel man!!!!
I seldom come across channels like these!
this guy explains everything which is awesome!
was searching for this my entire semesters! Finally got it out in 10 minutes. Kudos!
You just explained something my professors have struggled to for years in 10 minutes. Thanks a ton!
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
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!
Amazing video! You did an amazing job keeping us engaged and simplifying things.
You're a really good teacher. Thank you for breaking this down so simply! Please make more content :)
ok
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.
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!
Was struggling to understand the conceptual aspect of logs in my algorithms class, this video helped so much. THANK YOU!!
This is a fantastic explanation and display of applications of logarithms in computer science. Thank you for taking the time to make this!
sure
It is indeed very clear explanation and on point. Thanks a lot! it really helped me
sure
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
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.
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!
Thank you, Sir! Fantastic explanation!
sure
DUDE! This helped me so much!! Beginner coders of the internet appreciate you my dude!
buddy, ur channel, honestly , is the best channel for IT peopel... great thanks from the bottom of my heart !
This is the video that I always wanted but didn't know how to search for.
The explanation was just excellent bro
Thank you so much
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!
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.
Duuuuude, you just helped me pass my exams! I am forever grateful!
U a beast
Omg! The perfect explanation. It's clear, simple, and understandable
Wow. Perfect. I struggled with other explanations but this was very clear!
you're a legend mate!! thank you!
hey
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.
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
Incredible explanation, going to look through the rest for my interview prep. Thank you dearly
You're amazing, thanks!!!
ye
You just compacted two weeks of studying into 10 minutes, thank you
great
Seriously this is a GREAT job of explaining this rather difficult subject matter. Absolutely spot on wonderful! Thank you so much!
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
this is the best thing that happened to me
hahaha
I finally understand logarithms in time complexity!! Intuitive explanations like this are so helpful!
the way this man speaks and explains is exceptionally clear.
This is amazing omg ❤❤
hey
This is the best explaination I ever saw 😍💖🙏
thanks
dude you clearly have a talent to teach complex things in a simple to understand way. Great job 👍
What a simple and very clear explanation of logn. Thanks you so much!
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
no doubt, just one word, AWESOME :)
thanks
This is the best video to explain nlogn and logn time complexity.i was confused for over a year.
Man, this is the clearest explanation about log(n) i've ever seem. Thank you so much
Difference with nlogn and logn???
what
Finally! Extremely lucid explanation man! Loved it
Thanks a ton!
great.
Very detailed, I very much understood logalgorithms keep making amazing videos like these!
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
Beautiful! Finally, after all these years i understand this!
Clear Explanation! Very Nice. Thanks for this.
Thanks a ton for this video!! This cleared all my doubts related to log(n)
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 😀
Your explanation is just perfect, thank you!
Mindblowing explanation ever..Just cleared my mind.
This explanation is pure art, super simple short and efficient yet effective explanation. Love you man and keep up the good work.
Love it. Great explanation. Clear and concise. Thank you
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
Wonderful natural teaching style. Revealing some key intuitions for logarithms in CS. Thank you.
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) ❤
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 the best explanation I have ever seen. Great job
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 🙏
This is such an amazing explanation! I finally understand how this works. Thank you!
great and sure
Beautiful explanation my man! Thank you so much!
Dude, this explanation was as CLEAR AS WATER... After many years in the Comp Scie world, I finally truly understand logarithmic complexities
one of the best explanation i ever heard regarding why do we have logarithmic time complexity......Great Explanation...Thanks
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!
Thanks so much! Great explanation and presentation. Very helpful!
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
This is the only channel you need to watch to learn Complexity analysis. Nice work!!
thanks
Awesome job, you told me everything I needed to know in the first 3 minutes.
nice
by far one of the best educational videos. I really needed to try to understand this and you made it easy. thank you
Definitely the absolute best explanation, you made it so clear and simple a toddler could understand it!! Thank you very much!
Thanks for the clear explanation and examples. Finally I have an understanding!
Thank you, appreciate it 😄 Also check out our Free 5 Day DSA Interview Prep Mini-Course - backtobackswe.com/ 🎉
wow what a practical explanation of the topic. Thank you very much.
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
Now I understand log(n) complexity. Thanks a lot! It was great.
Thanks bro... This made me clear about logarithmic functions in time complexity of an algorithm
I love that instead of focusing on code you focused on the concept.
Thanks,I never got this concept, but you made it very simply and clear.
great
omg, I finally understand the general concept of this tern, many thanks to you
great to hear!
This is by far the best explanation of logarithms in time complexities. 👏
Thank you so much for your efforts and explanation. I finally feel like I understand what a log is, and it is soooo COOL!!!
Wow....thank you thank you on behalf of my math and CS teachers....Fantastic explanation!