Це відео не доступне.
Перепрошуємо.
Big O Notation Series #4: The Secret to Understanding O (log n)!
Вставка
- Опубліковано 17 сер 2024
- Non-recursive example:
• Big O Notation Series ...
Correction: There is a mistake in the return value of the logFunc() function. It should return a call to itself e.g. `return logFunc(n);` I have blurred out the mistake. Sorry for the confusion.
Big O Notation Series #3: In this video I will show you the secret to visualizing and understanding O(log n) or logarithmic complexity. After this video you should have a better understanding of how to diagnose algorithms with O(log n) or logarithmic complexity. The secret to understanding olog n.
More from this series: • Big O For Software Eng...
o(log n) explained big o notation big o big o notation explained log n o(log n) log n complexity log n time complexity log n time complexity example big o notation log n the secret to understanding olog n big o series big o mini series Join the Discord to talk to me and the rest of the community!
/ discord
![Дон ДОН, Алаудинов и СБЕЖАВШИЕ из под Курска ахматовцы 😁 [Пародия]](http://i.ytimg.com/vi/dEfCf5IK26Q/mqdefault.jpg)
O (log n) Explained with an iterative/non-recursive function: ua-cam.com/video/SfygqfMVSgw/v-deo.html
I don't understand why nobody is explaining it like this at our uni. Our Prof. is really good at making concepts look harder than they actually are. Thank you for the video.
😂yeah, for some people it’s more important to sound “smart” than to actually teach the concept. Thanks for watching!
Oh my days. I've been stuck on this for so long, and I finally figured it out. So in a binary search, each pass halves the data set. BECAUSE THE BASE IS 2!!!
Thank you so much.
😂 really makes me happy when I read comments like yours. Thank you 🙏
Same situation I was facing. But Now I also understand the trick.
I think it is important to note that the base does not have to be 2. If it is another base it can be reformulated as log base 2 of n multiplied by a constant so the order is still O(log_2(n))
Great explanation, but you gotta get rid of the hand. It's extremely distracting and adds nothing to the video
The marker/cursor is fine, but the hand is goofy as hell
I've just got that "oh" moment, it all clicked! thanks!
🤣 that’s awesome! I’m glad it helped 😆
Oh+++
Niceee
The big "oh" moment? (kill me)
Literally could not find any other videos for years on explaining these concepts at this simple of a level. Such a great job on this and excited to watch the rest of this series. Thank you for doing it!
Thank you! I hope you can get something out of the rest of the series 🙂
Very helpful video. Glad so many of us found use in it. The writing hand is a bit distracting but this video is a gem
Amazing. Came here for a refreshment and I have never saw that explained so simply. Thank you!
That’s great to hear! Thank you! 🙂
Ok, so I think I understand it.
The time complexity will depend on the efficiency of the algorithm. The time complexity can be used to say "how long will it take for this to be sorted?
or, in this case, how long until we reach our base case? (if (n===0) return "Done"; "
So, using this algorithm, the time complexity would be O(log N) , as N = 8 while O(log 8) = 3
If we used an algorithm that instead just subtracted 1 each time, our time complexity would be O(n), as it would take 8 iterations to reach our base case
Great video by the way. I had all the pieces from my reading but this just locks them all in place
This comment helped me get that "oh"
thank you
thanks
Thank you for this!!! 2 years in a computer science degree program just getting by when it came to this subject and watching tons of youtube videos..and here in less than 10 minutes I finally get it.
I’m happy to hear that. Keep it up! 🙂
The fact that the base is always 2 in CS is pretty key but I never came across it in an explanation until now!
I’m glad that you were able to come to an understanding! 😆
Think binary :)
no need to scratch my head anymore...I will recommend your channel to my friends as well who are from management background.....thank you so much...you saved me
That’s awesome! Thank you! Happy to help 😀
Your explanation is easy to understand.
These videos are very helpful 😃
Thank you
Glad it was helpful!
0:46 omg hearing that changed everything, I never knew we were always talking in base2 unless explicitly otherwise, that makes everything more clear thanks
Awesome! I’m glad that I could help 😎
If you would like to suggest topics for videos please feel free to let me know! Also, please like and subscribe if this video was helpful to you. I will continue to make more videos like this covering topics in computer science and software engineering so don't miss out!
great explanation! I've been trying to understand this for too long I finally got it, Thank you!
That’s really awesome to hear😆 I’m glad that the video helped you to understand! 🎉
OMG, After hours of looking at different videos, this method of teaching, explanation and visual representation made me understand Big O Notation. Thank you so much!!!
That’s awesome! No problem, I’m glad you were able to understand it 🙂
Bruv, this is the best explanation i can find on UA-cam.
Thank you very much
That’s good to hear! I’m happy to help bro 🙂
Yes I would like to see how this works with a non recursive function!
Sure! I will try to make a video explaining this soon :)
Hello! Sorry for the delay. I've completed the video that explains O(log n) with a non recursive function! You can find it here: ua-cam.com/video/SfygqfMVSgw/v-deo.html
@@kantancoding wow you were serious lol, thanks!
😉
@@kantancoding Thanks, King!
Why did I not find you sooner? Sir, you have explained this in such a manner that even a 5yr old will understand. Subbed immediately.
Thank you! I’m happy to help 🙂
I have stuck at this point for a really long period of time. Thank you so much for your detailed explanation! It finally makes sense to me.
That’s great! Really happy to help somebody get over the hump! 🙂
Absolutely brilliant! I especially liked how you explained the idea of a logarithm and WHY people just say it's the inverse of exponentiation. I doubt most people actually understand it this way. Thank you! This helped me a lot since I have little to no mathematical background.
That’s great! I was in the same boat when I learned this which is why I made these videos so thank you for the feedback. It really helps me out 🙂
@@kantancoding Thank you so much, your videos really made things much clearer for me regarding Big O and Sorting. Even your single video on Graphs and Adjacency Matrix was very fruitful. Shout out to the FCC channel for featuring your Big O course. Please continue uploading, I'm sure you'll get a huge audience over time.
Have a great day ahead.
Oh my god, thank you so so so much! Like the comment before, this video was my big "oh" moment. Haha, see what I did there? Seriously though, thank you the explanation was so much more simple to understand. My textbook made me want to cry!
Great job! I'm glad you came to an understanding 😀
I'm surprised this doesnt have more views. this is amazin
Thank you 🙂
Even this video 2 years old, it still helps me today! Thanks!
😂 fortunately, these concepts don’t change as time passes. Thank you!
These videos are just amazing!
Really thanks for the nice explanation
Thank you for giving them a chance! I wanted a series like this when I was learning this stuff so I’m happy that people find it useful 🙂
thank you man, I have been at this for so long
Glad I could help 🙂
I wish if there was some way i could give this video 100 likes. I was some how was able to understand O(n), O(n2) and cube. this video made me clear on O(log n). Thanks a lot.
That’s awesome！ I’m really happy that you were able to come to an understanding 🙂
I mean you could make a bot that makes 100 accounts and likes this video on all of them ;)
Watched so many videos yet this 5 minutes video opened my mind lol
I’m glad that you were finally able to make sense of it 🙂
Thanks you🖤. Love from Bangladesh
Hi! From Argentina i see your video!! Thank u soo much! Now i am going too se the iterative video
Thank you 🙂
Finally I've met the channel I need
understood in one go...really good explanation...thanks😁
No problem! Happy to hear that 🙂
This is the perfect explanation.
Thank you!!
Man, these videos are a blessing. Thank you!
I’m really glad they’re useful!
Very nice video. Finally I understand the concept of O (log n)
Nice! keep it up 🙂
YES , make videos on how O(log n) works on non recursive function.
Thanks for your feedback! I actually already did: ua-cam.com/video/SfygqfMVSgw/v-deo.html
@@kantancoding you are awesome❤️❤️
☺️ thank you 🙏
Awesomely explained
Thank you 😊 happy it helped
Best Explanation💯💯💯
Finally a good explanation! Thank you so much for this!
No problem! I’m glad that the video helped you 🙂
Nice break down, all you need to do is actually look for division within the algorithm to realize it isn't linear.
So briefly, logarithm is a way to say how many computations you need to perform for your input n. Given the problem where we divide 8 recursively by 2, by logarithm complexity we are saying that for our input 8 we need to do 3 computation (function calls / iterations) to get our final result (each computation is just a function call where we divide current number on a stack frame by two)
“Logarithm is a way to say how many computations you need to perform for your input n”
This is actually incorrect. That’s not what a logarithm is. That’s more of a definition for how we measure the complexity of a function and/or algorithm.
A logarithm is the exponent or power that we need to raise a base to in order to produce a given number.
Big O of Log n means that we need to raise the base 2 to some power to get n, and that power that we need to raise 2 to in order to get n is the number of operations or in your words “computations” that need to be performed for the input n.
But actually, it’s not exactly the number of computations or operations because we only take into consideration the highest order part of the function/algorithm. So there may be a bunch of constant operations that we ignore for example.
Hope it helps! 😉
I love you bro ❤, Love the way you teach!
I'm happy to help bro! Keep up the good work 💪
Its so sad that my algorithm teacher never explained this, thank you!
Gotta love those teachers that don’t actually teach 🫠
super explaination, sehr gut
Isn't it 4 levels deep? It doesn't stop at logFunc(1) since the base case is n === 0, and the only time n changes is when it is halved, so n = Math.floor(1/2) = 0, then return logFunc(0) where it will hit the base case. Idk if this is a mistake or not but it's causing me confusion.
Watch the 7th video in this series where I explain the time complexity of recursive Fibonacci and pay close attention to what I say about constants 👍
@@kantancoding I watched the Fibonacci video, and if I understand correctly, basically it may be true that it runs one more time, maybe it doesn't. In any case, because its a constant of +1 or +0, we don't care from a big O notation perspective.
Maybe 3 levels vs 4 levels seems like a big difference (33%), but that's only with an N of 3. As we go reach an asymptotic scale (infinite), that +1 is negligible, so we ignore it.
That said, I also would have thought the base case should be written as n===1, but in any case, the last run is irrelevant. Am I thinking about that correctly?
Thanks for the tutorial, but what is being blurred out ? I just want to copy the code and see it working. If you could tell me that would be much appreciated :D
Best explanation ever
Thank you 😊
Thanks bruh, exactly what I looked for
Glad I could help bro
Thank you for the explanation!
But I am a little bit confused to the example.
the whole function actually runs 4 times , no matter what level it has,
so I don't understand how does it count as 3.
Yes I am also confused by this!
Please watch the rest of the series and pay close attention to the explanations about ignoring constants 🙂
Just what i needed. 10/10 explanation
Thank you! 🙏
Keep up the great work man, very good explanation and example. I hope you keep uploading videos and help us learn :) As a guy with no math background trying to learn Java you are very helpful
Thank you! Btw you don’t need a math background so just keep at it 🚀🙂
Great video. But there s still something I don t get, when we got to level 3 won t the function call itself one more time ( since the stopping condition is n===0 and n is qual to one ) and we will go down one more level then because n is equal to zero we stop
The function will indeed go down another time on 1 but because it's applying Math.floor the next time it goes down it will go down as zero since 1/2= 0.5 and the function will stop. I hope that makes sense for you
@ thank you
@ But it still runs the whole function 4 times, no matter is it gonna stop at the 5th calling?
Good content, Keep working like this, Thanks.
Thanks, I’m glad it was helpful 🙂
How can you move your hand so fast and write so perfectly 🤯trippy af
That’s that 🧈 breh
Really useful thanks keep going do more tutorials like this!)
Thank you for supporting 😊
Beautiful breakdown 👏
Thank you so much sir for providing valuable content.
Your explanation technique is so awesome.
Salute by heart 💜
Thank you! I’m really happy to hear that ❤️
This is very great and clear. Thanks! Keep up ✊🏾
Thank you 😊
Super cool! base is 2 as default that I didn't know all the way.
Thank you!
Very useful video. Thank You so much..
Happy to help 🙂
Thanks for the nice explanation. But I have a question. How could I know I need to approach this with logarithm among many time complexities?
Well basically you need to learn the other complexities as well. This video is actually part of a series. You should go through the entire series from start to finish to get a complete understanding.
What about the time complexity for
For(into I=0;I
I think you'll find your answer here: ua-cam.com/video/SfygqfMVSgw/v-deo.html :)
Thanks brother ❤️❤️❤️❤️❤️❤️❤️❤️
I came here trying to understand O(log n) and I think I came out a little more confused. I was trying to find out why in binary search the upper bound is O(log n). Why in upper bound for binary search does it use O(log n) but in your example O(log n) is shown as recursion?
Hmm, I think you have the wrong idea about how this works. Regardless of if the algorithm is binary search, or any other algorithm, O(log n) is O(log n).
If you learn what that means, you can apply that knowledge to the binary search algorithm.
This video teaches what O(log n) is.
Question: So in the example function, if the division was by 3, does that mean that the time complexity is log3(n)? (log base 3 of n)
Consider this: Log base 2 of 27 = log base 3 of 27 / log base 3 of 2 = C * log base 3 of 27 where C is a constant equal to 1 / log base 3 of 2. So because log base 2 of 27 and log base 3 of 27 only differ by the constant C, and because in Big O we ignore constants, they are both valid. So the base doesn’t matter but in my opinion, base 2 is more intuitive and more widely used in computer science
Great explanation
❤️
Commenting to know if my understanding is on the right way to think about o(log(n)),correct me if I am wrong:
So we could say that an algorithm is running in o(log(n)) time if its way of computing/processing ,halves the given data structure at each iteration leading to the time complexity being the number of times the data structure could be divided into half I mean the log(n) times . Like in binary search we reduce our search space to half.
And I have follow up question :
So is this kind of reduction of processing space of the data structure is always half or do we have the possibility in reducing it in 3,4,5 parts at each iteration causing log3(n),log4(n) .....??
Thanks in advance
It’s important not to mix up time and space complexity. They are separate from one another. That is, a function can have a different complexity for its time and a different complexity for its space.
As far as the base of the log is concerned. Regardless of the base we would still say it’s log(n). There are a couple of comments that I responded to in this video’s comments section where I’ve explained that part in more detail.
Thanks for your questions and thanks for watching! 😊
I thought o(n) is number of operations for n elements so if 10 elements then 10 operations. And likewise O(logn) would be if 8 elements then 3 operations . What am I missing here ?
I mean I would explain it all in this comment but I already explained it all in the video series. So I’d recommend just watching the entire series 🙂
You are saving my grade THANK YOU
Hope you got a good grade!
Hi, I have come across videos of lectures saying that a for loop of (int k =1; k
Yeah, In CS we usually use base 2 as opposed to something like base 10 which is commonly used in mathematics. So if the base isn’t explicitly written… you can assume base 2 in CS. Just think about how memory and stuff like that is done in computers. It usually increments by 2 to some power. 2^1, 2^2, 2^3, 2^4, 2^5, 2^6 which is 2, 4, 8, 16, 32, 64… respectively. When you buy an SD card, you don’t buy a 60gig card.. you buy a 64 gig card. When you buy a new laptop, you don’t upgrade to 10 gigs of ram, you upgrade to 16 gigs of ram. Hope that helps! 😊
@@kantancoding Thank you so much, sir!! This really helped my understand and makes it easier to remember why 2 is often assumed as base with the base 10 example.
Great video man!
Thank you 🙏
Thank you
I'm confused. How does this relate to master theorem?
such a good explain sir
Thank you sir 🙂
Incredible explanation !
Thank you! 🙂
Thank you....
Great content bro, thank you..
My pleasure! Thank you🙂
Nice vid man, Easy to understand!
Great! Thank you for your feedback 😁
finally, excellent explanation! great job!
Thank you! I'm glad it helped :)
this was phenomenal. thank you so much!
Thank you! I’m glad it helped 🙂
Wow thank you so much
No problem! Thanks for watching 😎
MASSIVE VIBRATING ARM
wow thank you !
very good visual, thanks this was a great video.
Thank you 🙏 I’m glad that you liked it 🙂
amazing example and visualization
Really happy to hear that! Thank you 🙏
perfectly explained
Great video
Thank you very much 🙏
Thank yous so much!
My pleasure 🙂
Thank you for the video!
Of course! Happy to help 😎
Thanks
Wonderful! Thanks!
at 4:24 why do you say 2 = 8/2 and 2= 4/2 and 2=2/2? I did not follow that step
Please see the multiplication signs between the 2s
I still don't understand what the O is for. And when does a function not equal 0(log N)?
I’d suggest watching the whole series and maybe some alternative resources as well 🙏
A very good explanation, keep it up
Thanks, will do!
damn..so this guy really be out here saving my grade..
🤣 this comment is 🔥. I’m glad I could help you out. You got this, keep putting in work 💪
Pls add similar kind of video for non recursive functions for calculating the O(login)
Hey, I already made a non recursive one. Please see here 🙂 ua-cam.com/video/SfygqfMVSgw/v-deo.html
You're a god
😂 I’m glad I could help!
What if there in function will be Math.floor(n / 3) ?
I'd say that this is just changing the base from 2 to 3 which would still be O(log n) regardless of base in Big O