Big O Notation Series #10: Log n Complexity Explained With An Iterative Function [Logarithmic time]

Log n Complexity Explained With An Iterative Function: In this video, you will learn how an iterative function can have a time complexity of O(log n).
More from this series: • Big O For Software Eng...
logarithms logarithmic time logarithmic time complexities logarithmic space complexities logarithmic complexities software engineering computer science programming programming interviews coding interviews coding questions algorithms algorithmic thinking google internship facebook internship software engineering internship swe internship big n companies logn order logn logn complexity complexity analysis time complexity time complexity basics algorithm basics sorting algorithm complexity binary search complexity why logn in time complexity Join the Discord to talk to me and the rest of the community!
/ discord

[@asmmeto55]

As a self-taught, I watch a lot of tutorials on UA-cam, so I can say that I know high-quality content when I see it. And this right here is a gem! Keep it up, man. I just came from the other O(log n) video and I LOVE your channel!

[@kantancoding]

Hey thank you! That means a lot to me ☺️. Thank you for taking the time write this comment. Really made my day 😆

[@sagarjani8760]

Just wanted to say that your videos are amazing and have a great quality content. Your skills to explain things in a simple way is very rare. Please keep going and making such videos.

[@kantancoding]

I'm really happy to hear that! Thank you very much for your kind words 🥲

[@mrindia4178]

This makes more since for me, the recursive one was kinda hard to understand... Awesome videos! Why do you have such less subs? you should have at least 100k

[@kantancoding]

I guess my videos aren’t good enough yet 😂 I’ll try to improve them. Thanks for your support 🙂

[@eleandro]

Wow bro! This is the best explanation I've found! Congrats!

[@kantancoding]

Thanks bro. Happy to help 🙂

[@vivekshah2569]

Got much clarity .....Thank uh

[@eudeamonism]

🎉

[@josevalente1667]

amazing

[@danbdex1066]

Brilliant mate, thanks it just clicked for me :)

[@kantancoding]

Awesome! 😃

[@tanduong6092]

What about different kinds of inputs? Arrays, strings, etc. i’m having trouble applying this to other inputs. Thank you!

[@kantancoding]

It might help to watch the entire playlist! 😊

[@kostabakalinov1237]

very helpful man! keep up the good work

[@kantancoding]

Thank you 🙏 I’m glad that I was able to help 😆

[@helltrooper1288]

What if the base is different? for example n = 27, and the function divides by 3. Would it still be O(log n) with a base of 3?

[@kantancoding]

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

[@TotoPotoRoto]

@@kantancoding thank you very much. I can't thank you enough for this explanation.

[@abba5102]

Very good

[@kantancoding]

Thank you!

[@nahlayasmine924]

Thank you

[@kantancoding]

my pleasure 🙂

[@arjay_2002]

Thanks!

[@kantancoding]

My pleasure 🙂

[@poornachandra1127]

Will the time complexity change if we had while(n > 2) with n value as 8?

[@kantancoding]

Think about it like this. If n were 1 million, would changing the the code to while(n>2) make a difference in how the function scales?
When you say “with n value as 8” that would mean that n is a constant which would mean the entire func would be O(1)

[@poornachandra1127]

Thanks for your reply..I am trying more to understand what would happen if n/2 becomes n/5 or n/6 or for that matter n/x where x can be any number..how can i understand time complexity in that scenario..will it be log n to base x in that case?

[@kantancoding]

@@poornachandra1127 if it were n/6 for example, the complexity would be log base 6 of n which we would still consider O(log n).
For example if the function does n/6 and n=10, log base 6 of 10 would be 1.28509720... which is about how many iterations the function would need to do because 6 to the power of 1.28509720 is about 10~. So the function will scale logarithmically. More specifically O(log base 6 of n).
To use a rounder number example, if the function does n/6 and n = 216, it would be log base 6 of 216 which equals 3... so we would need to do 3 iterations in the function which means we would need to do 216/6.... 36/6.... 6/6... until we finally arrive at 1. So regardless of the input "n", the function will scale at a rate of O(log base 6 of n) which is O(log n).
It will be the same regardless of what we divide by. The base of the log will change but it doesn't matter.
Hope that helps!

[@poornachandra1127]

@@kantancoding thankyou..this information is what i was really looking for..it helps 😊

[@colinrickels201]

So if we divide in by three is it then O(log n) with base 3

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