Big O Notation Series #4: The Secret to Understanding O (log n)!

[@kantancoding]

O (log n) Explained with an iterative/non-recursive function: kzbin.info/www/bejne/iZfcmKScgruGndk

[@ashtonb561]

Great explanation, but you gotta get rid of the hand. It's extremely distracting and adds nothing to the video

[@subyouwont]

The marker/cursor is fine, but the hand is goofy as hell

[@jubjubfriend64]

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

[@kantancoding]

Awesome! I’m glad that I could help 😎

[@kantancoding]

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!

[@Cobain7House]

I've just got that "oh" moment, it all clicked! thanks!

[@kantancoding]

🤣 that’s awesome! I’m glad it helped 😆

[@asishankam6552]

Oh+++

[@kelvinmaxwell6385]

Niceee

[@thijshamersma]

The big "oh" moment? (kill me)

[@ishanpatel5388]

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.

[@kantancoding]

😂 really makes me happy when I read comments like yours. Thank you 🙏

[@swarnenduchatterjee721]

Same situation I was facing. But Now I also understand the trick.

[@derpnerpwerp]

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))

[@t6hp]

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.

[@kantancoding]

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 🙂

[@t6hp]

@@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.

[@ozankaya7718]

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.

[@kantancoding]

😂yeah, for some people it’s more important to sound “smart” than to actually teach the concept. Thanks for watching!

[@shubhamkumarsingh2290]

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.

[@kantancoding]

Thank you! I’m happy to help 🙂

[@karthiksrinivas5980]

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.

[@kantancoding]

That’s awesome！ I’m really happy that you were able to come to an understanding 🙂

[@connerreimers6506]

I mean you could make a bot that makes 100 accounts and likes this video on all of them ;)

[@jaredlmayer]

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!

[@kantancoding]

Thank you! I hope you can get something out of the rest of the series 🙂

[@edenmeresman5619]

Hi! From Argentina i see your video!! Thank u soo much! Now i am going too se the iterative video

[@kantancoding]

Thank you 🙂

[@coxandrewj]

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

[@MaulLerGamer]

This comment helped me get that "oh" thank you

[@declinesgt8693]

thanks

[@bronzebond4869]

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

[@michaeltkachenko7313]

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)

[@kantancoding]

“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! 😉

[@karssr]

Its so sad that my algorithm teacher never explained this, thank you!

[@kantancoding]

Gotta love those teachers that don’t actually teach 🫠

[@kittoh_]

This is the perfect explanation.

[@kantancoding]

Thank you!!

[@KShweZin]

Super cool! base is 2 as default that I didn't know all the way.

[@ninjarogue]

Yes I would like to see how this works with a non recursive function!

[@kantancoding]

Sure! I will try to make a video explaining this soon :)

[@kantancoding]

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: kzbin.info/www/bejne/iZfcmKScgruGndk

[@ninjarogue]

@@kantancoding wow you were serious lol, thanks!

[@kantancoding]

😉

[@astrix8812]

​@@kantancoding Thanks, King!

[@nahlayasmine924]

Your explanation is easy to understand. These videos are very helpful 😃 Thank you

[@kantancoding]

Glad it was helpful!

[@stiffyBlicky]

This video could have been great, but the stupid hand you used made this video unwatchable.

[@gingergiant89]

The fact that the base is always 2 in CS is pretty key but I never came across it in an explanation until now!

[@kantancoding]

I’m glad that you were able to come to an understanding! 😆

[@user-pe9qg3hg3k]

Think binary :)

[@codingTutz]

Best Explanation💯💯💯

[@BTypeGuy]

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.

[@kantancoding]

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 👍

[@Mario_Speedwagon]

@@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?

[@FKstudiofan]

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

[@FKstudiofan]

@ thank you

[@陳大文-z8x]

@ But it still runs the whole function 4 times, no matter is it gonna stop at the 5th calling?

[@陳大文-z8x]

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.

[@BTypeGuy]

Yes I am also confused by this!

[@kantancoding]

Please watch the rest of the series and pay close attention to the explanations about ignoring constants 🙂

[@jabir5768]

How can you move your hand so fast and write so perfectly 🤯trippy af

[@kantancoding]

That’s that 🧈 breh

[@RLLRRLLR]

Amazing. Came here for a refreshment and I have never saw that explained so simply. Thank you!

[@kantancoding]

That’s great to hear! Thank you! 🙂

[@dr5832]

great explanation! I've been trying to understand this for too long I finally got it, Thank you!

[@kantancoding]

That’s really awesome to hear😆 I’m glad that the video helped you to understand! 🎉

[@russ7k]

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

[@vivekshah2569]

Thank you....

[@chastitykeniston8150]

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!

[@kantancoding]

Great job! I'm glad you came to an understanding 😀

[@Nanis-World]

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.

[@kantancoding]

I’m happy to hear that. Keep it up! 🙂

[@drumsmaaan]

I'm confused. How does this relate to master theorem?

[@vicliur2]

Wow thank you so much

[@kantancoding]

No problem! Thanks for watching 😎

[@Jaime-xd4mj]

Thanks for the aclaration "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." I was driving myself crazy until I read the description.

[@kantancoding]

Yeah, that was my bad! Glad the comment helped 😊

[@MrNams]

Vedy good video, but that animation is loosing concentration

[@kantancoding]

😂 yeah, I’ve had many complaints about that. Too late to change it now

[@genjimccorkle5518]

Nice break down, all you need to do is actually look for division within the algorithm to realize it isn't linear.

[@znb5873]

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)

[@kantancoding]

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

[@akshykumar1118]

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

[@kantancoding]

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! 😊

[@adnaneguettaf5461]

A very good explanation, keep it up

[@kantancoding]

Thanks, will do!

[@brianmsantos]

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?

[@kantancoding]

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.

[@_AbrarFahim_A]

Thanks you🖤. Love from Bangladesh

[@hemanthkumark6981]

Awesome thanks a lot, Well Explained!...

[@kantancoding]

My pleasure! Glad I could help 😆

[@yebonbyun7648]

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?

[@kantancoding]

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.

[@dimar4150]

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 ?

[@kantancoding]

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 🙂

[@Giorgi.Japiashvili]

Really not a good idea to put an exclamation mark here, where it could be mistaken for a factorial

[@kantancoding]

Sure man, good point 👍

[@divinomatheus6212]

These videos are just amazing! Really thanks for the nice explanation

[@kantancoding]

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 🙂

[@Brandon-vr7xf]

Hi, I have come across videos of lectures saying that a for loop of (int k =1; k

[@kantancoding]

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! 😊

[@Brandon-vr7xf]

@@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.

[@thestrappingentrepreneur2822]

i feel like this helped but not enough. wish there was a graph ond none recursive my Prof never uses recursive

[@kantancoding]

I have a video with an iterative(non-recursive) example. Added the link to the description. Hope it helps!

[@julietonyekaoha402]

Very good explanation. thank you. One thing though is that the function (logarithmicFunc) you're calling after the return statement has a different name from the main function (logFunc), I think you should find a way to update that to avoid confusion. Also, I'm interested in the non-recursive example, looking forward to it.

[@kantancoding]

Oh wow, you're right. I definitely need to find a way to fix this. Thank you for your sharp eye and thank you for your comment! And I will get started on a non-recursive example. Thank you!

[@kantancoding]

Unfortunately, it seems the best option is to re-upload. Best I can do is blur the return function otherwise which I'm afraid will still be quite confusing for a new learner.

[@julietonyekaoha402]

@@kantancoding You don't need to blur the function. You can add an info tag (I'm not sure what to call it) that points to the return function name, correcting the name. Just like it's done in some video courses. Also, leave a note on the correction in the description box.

[@kantancoding]

@@julietonyekaoha402 Yeah, I actually thought the same because I've seen that done in videos before as well but I can't find the feature in youtube studio. Either I don't have access to that feature because my channel is too small or it no longer exists :(.. It's also possible that I just missed it but I've looked all over and I've searched online for the above feature as well. I ended up patching it up with the blur effect. If it is too confusing i will just re-upload.

[@julietonyekaoha402]

@@kantancoding I just rewatched the video, the blur effect works quite well. Good job. I'm writing an article on the different Big O Notation complexities, I will reference your video on it as I find it very useful. Thank you.

[@mehdi-vl5nn]

5:04 must be 1 not 0

[@BTypeGuy]

That's my exact thinking. It doesn't stop at logFunc(1) like he states, it stops at logFunc(0) which is when it hits the base.

[@mehdi-vl5nn]

​@@BTypeGuy I did not gain anything from that video but later on, I found it out all about "logn" things, consider some loop or actually any algorithm that contain either a multiply or divide then the time complicity always end up as logn ex: n/3 -> log base 3 n ..

[@nathangray-bain8472]

I still don't understand what the O is for. And when does a function not equal 0(log N)?

[@kantancoding]

I’d suggest watching the whole series and maybe some alternative resources as well 🙏

[@artonext]

Really useful thanks keep going do more tutorials like this!)

[@kantancoding]

Thank you for supporting 😊

[@Shubhendu-pj5hz]

less info but lot of unnecessary animation wtf

[@kantancoding]

Chill

[@aryankumar313]

understood in one go...really good explanation...thanks😁

[@kantancoding]

No problem! Happy to hear that 🙂

[@rasheedmohammadalialjufi4999]

What about the time complexity for For(into I=0;I

[@kantancoding]

I think you'll find your answer here: kzbin.info/www/bejne/iZfcmKScgruGndk :)

[@himanshukhullar9145]

great vid ,try making it before hand on dood.. , may look better. Great work!

[@kantancoding]

Thanks for the tip

[@ixcheck13]

this is why I work construction 🤣

[@madelynhillier8563]

at 4:24 why do you say 2 = 8/2 and 2= 4/2 and 2=2/2? I did not follow that step

[@kantancoding]

Please see the multiplication signs between the 2s

[@SkomeshLive]

Decent video however the digital hand drawing everything is very jarring

[@kantancoding]

I’m aware. The video was made 2 years ago. Hope it helped you 🙂

[@dylanngo4454]

Good content, Keep working like this, Thanks.

[@kantancoding]

Thanks, I’m glad it was helpful 🙂

[@personalpairprogrammer7915]

great explanation but I feel like someone who needs help with this concept has a high probability of not knowing recursion.

[@kantancoding]

Hey, thanks for the feedback. Did you check the pinned comment?

[@personalpairprogrammer7915]

@@kantancoding 😬😅

[@abdullahwaqar3024]

YES , make videos on how O(log n) works on non recursive function.

[@kantancoding]

Thanks for your feedback! I actually already did: kzbin.info/www/bejne/iZfcmKScgruGndk

[@abdullahwaqar3024]

@@kantancoding you are awesome❤️❤️

[@kantancoding]

☺️ thank you 🙏

[@561Aloha]

I'm surprised this doesnt have more views. this is amazin

[@kantancoding]

Thank you 🙂

[@Rei-m3g]

my time complexity of learning this topic is exponential .

[@kantancoding]

😂 give it time. It will click, and when it does you’ll realize that it’s actually not so difficult. I didn’t understand it when I was first introduced to the topic either

[@butterchicken9297]

Watched so many videos yet this 5 minutes video opened my mind lol

[@kantancoding]

I’m glad that you were finally able to make sense of it 🙂

[@mikhailkuzmin2431]

Thanks bruh, exactly what I looked for

[@kantancoding]

Glad I could help bro

[@sepsmusic]

Bro, from the title I thought you meant O(log n) factorial haha

[@kantancoding]

😂🤣🤣 I was wondering when somebody would mention that. I read the title recently and thought the same thing

[@rajeshkumarjena4837]

Very useful video. Thank You so much..

[@kantancoding]

Happy to help 🙂

[@lunatunny7594]

MASSIVE VIBRATING ARM

[@РоманСарваров-ч5л]

What if there in function will be Math.floor(n / 3) ?

[@kantancoding]

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

[@RamakrishnaValandasu-po3on]

thank you man, I have been at this for so long

[@kantancoding]

Glad I could help 🙂

[@nadeelnarayana110]

Thanks brother ❤️❤️❤️❤️❤️❤️❤️❤️

[@humanrobotinteraction2732]

If you look closely you can see that hand is not real.

[@kantancoding]

😂 Yeah, the hand is definitely an animation

[@prachijoshi1910]

Please make a video for non recursive function

[@kantancoding]

Hope you found it. It should be in the description 🙏

[@timborg770]

That hand is suuuuper annoying! My gosh!

[@kantancoding]

😂 yes I know. Many people have already complained about it. Either way, hope you were able to get something out of it.

[@helltrooper1288]

so whats the blurred part in the last line? lol

[@rahulchandna3242]

by mistake he wrote logarithmicFunc instead of logFunc, so he blurred the "arithmic" part

[@rajibkundu1]

I love you bro ❤, Love the way you teach!

[@kantancoding]

I'm happy to help bro! Keep up the good work 💪

[@vamshidharreddy7321]

super explaination, sehr gut

[@jamilmuhanna8792]

wow thank you !

[@premhulikoppe1470]

Great content bro, thank you..

[@kantancoding]

My pleasure! Thank you🙂

[@makleigiant4100]

correct me if im wrong but i think the explanation u give in the end about line 5 is wrong cause when n=1 u still gonna divide and so the result will be 0.5 but when u floor that its just 0 and then u exit after the function runs for 0 as well since u return "done". Otherwise good job on the vid

[@kantancoding]

Hmm not sure what you mean. What I’m saying is, we want to stop when n=1 so if n becomes 0, immediately after we enter the function we return done. If you remove that line, it will keep dividing fraction after fraction or 0/2 over and over which will always be 0 until you run out of memory. The function is short so you can write it out in a code playground or something and remove that line and observe the behavior. Aside from that, thanks for your comment. I’m glad you enjoyed the video 😎

[@makleigiant4100]

@@kantancoding u still saying that it stops when n=1 but in reality the last time you get into the loop is when n=0 u just dont finish the loop u return.

[@makleigiant4100]

@@kantancoding btw i scored 100 on my exam thanks a lot

[@makleigiant4100]

@@kantancoding yeap i fully understand that but if u returned n instead of done you would return 0

[@makleigiant4100]

​@@kantancoding quote "all it does is make sure that we stop dividing when n becomes 1" but in reality it stops when n becomes 0 4:55

[@murugesh1915]

Nice one

[@ashs3979]

Thank you!

[@Pragnesh_Lavantra]

Thank you so much sir for providing valuable content. Your explanation technique is so awesome. Salute by heart 💜

[@kantancoding]

Thank you! I’m really happy to hear that ❤️

[@Kinggaming-hp3qp]

such a good explain sir

[@kantancoding]

Thank you sir 🙂

[@Dhanushsaji]

Thank you

[@Webmer]

Hey man please make a video for non recursive functions

[@kantancoding]

I actually already did! Here’s the link kzbin.info/www/bejne/iZfcmKScgruGndk

[@Its_Hack]

Thanks

[@Chasing_the_wind]

Bruv, this is the best explanation i can find on KZbin. Thank you very much

[@kantancoding]

That’s good to hear! I’m happy to help bro 🙂

[@Johann_Demian]

Nice

[@sidandhawa]

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!!!

[@kantancoding]

That’s awesome! No problem, I’m glad you were able to understand it 🙂

[@martapfahl940]

Awesomely explained

[@kantancoding]

Thank you 😊 happy it helped

[@rnayla1858]

Best explanation ever

[@kantancoding]

Thank you 😊

[@venkatasubbareddyn17]

Pls add similar kind of video for non recursive functions for calculating the O(login)

[@kantancoding]

Hey, I already made a non recursive one. Please see here 🙂 kzbin.info/www/bejne/iZfcmKScgruGndk

[@gabealberro6081]

man why did you title it O(log n)! when youre not covering factorial

[@kantancoding]

I did cover factorial. It’s in a separate video in the series ;)

[@renadnasr7091]

Thank yous so much!

[@kantancoding]

My pleasure 🙂

[@neetideora7195]

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

[@kantancoding]

That’s awesome! Thank you! Happy to help 😀

[@davidlira8853]

Beautiful breakdown 👏