Big O Notation Series #5: O (n log n) explained for beginners

[@brucewayne3141]

To those who are confused about how log works, it's basically like splitting a log. All it's asking is how many times do you have to split the big number by the small number to get down to 1. for example log base 2 of 4 basically means that you have to split 4 by 2 two times to get to 1. another example would be log base 4 of 64, you have to split 64 by 4 three times to get down to 1 single wood log piece.

[@abdullahalaraz7404]

Thank you very much for this explanation. Now I understood how log works

[@ahmadafghan6767]

explained better than the video itself.

[@sharafat-karim]

legend! thanks man

[@t6hp]

This is a brilliant analogy, thank you so much!

[@LE-do5by]

Thanks

[@c4bantle1]

Please do not stop making videos! You are the first person to explain this to me in a way I truly understand! Thank you so much!

[@kantancoding]

I’m really happy that you understand now! Thank you 😊

[@techhdan]

I've been programming for over a decade but never took the time to understand Big O notation. I landed a Google interview next month and I'm finding myself in a critical timeline to learn algorithms and Big O notation. These videos have been amazing at explaining these concepts very simply. I cannot thank you enough. This is amazing.

[@kantancoding]

Congratulations! I’m glad that they are helpful. I’m sure you will do great 🙂

[@WaldoTheWombat]

How did your interview go?

[@techhdan]

@@WaldoTheWombat I unfortunately did not pass but they did say I'd be given another chance next year. My test had nothing to do with Big O notation but instead i had to do a breadth first traversal on a matrix and at that moment i hadn't studied graph algorithms. I'll be ready by next year! 🤜

[@WaldoTheWombat]

@@techhdan sorry to hear that, good luck next time. a matrix is a 2d array though, so what do graphs have to do with it?

[@techhdan]

@@WaldoTheWombat i was given a matrix with each element representing land or water. Given a coordinate find if the element is a lake and if so return the area of the lake. With a breadth first traversal you can count all the sorrounding water to get the area. Graphs can be represented as a multi dimensional array.

[@whatya2301]

You should know that your channel is soon going to grow crazy. Loved the content. Especially the graphic part and the tools used makes the concept so much more clear. More power to you.

[@kantancoding]

Thank you. Your comment is encouraging. I’m glad that it helped you out!

[@shubhanshusahuu]

Best video to understand n log n

[@Theodore2303]

Watched your explanation on Big O of Log N, then I watched this. Now I understand! Thank you!

[@kantancoding]

That's awesome! Great job and keep up the good work!

[@thomasgipson7120]

This helped me so much. Most creators don't go into O(log n) or O(n log n) but you did and you did it in a way that I was able to understand and retain. Thank you!

[@kantancoding]

Thank you! Really happy to hear that 🙂

[@markbarlescu1853]

After 3 previous videos from other creators. Yours is the one that’s most coherent, and finally had it click for me. Thanks!

[@kantancoding]

Happy to be a part of your aha moment 🙂

[@TheRescue4study]

You are legend man.....!!!!!!!!!! FULL STOP. Tried to learn logarithms in time complexity no one ever explained log like you.

[@kantancoding]

That’s awesome. When I was learning, the explanations didn’t work for me either. Glad you came to an understanding!

[@mayankughade3585]

Man, you just cleared off a reallly big QUESION MARK from my head !!!!!! Thanks a lot.

[@kantancoding]

I’m glad to hear that! Keep up the good work 🙂

[@AmeerHamza-mz3cg]

Thanks, I finally understand O(nlogn). I never truly understood it in uni but this vid helped me alot. Stay Blessed 🥰

[@kantancoding]

Gotta love uni. The place where you pay to teach yourself 🫠

[@maiaklimenko6614]

I am 10 seconds into your video, and I already understand what n log n is. Wow, just wow

[@kantancoding]

😂that’s awesome! I’m happy that you came to an understanding 🙂

[@lillyput2275]

U r just a life saviour🙇🏻‍♀️ may god bless u🧚🏻‍♀️

[@kantancoding]

Happy to help 🙂

[@demiguo3156]

Your vids are one of the best cs topic explanation vids I've ever seen on the tube! You explain it so well and so clear, especially with your calm voice and incredible graphics. You made my life as a cs major college student so much easier, thank u!

[@kantancoding]

I’m glad to hear that they are helpful to you 🙂 thank you!

[@prakashpangeni8153]

You are awesome ! Simply brilliant 🙏 Never understood this until I encountered your videos... Please make more such videos to cover DSA topics.

[@kantancoding]

Hey! Thank you! I’m glad it helped. More algo & ds videos coming soon 😊

[@eleandro]

You're so good in your explainations that I don't have any questions.

[@kantancoding]

Hey, I’m glad it helped! Thank you 🙂

[@JamieDawsonCodes]

I loved the code example + visuals for this. It's extremely easy to understand.

[@kantancoding]

Awesome! Glad it helped you out 😎

[@mobileminimaster3015]

Great video man. Was dying without understanding what the hell they meant. Now I'm so clear. Thanks a ton.

[@kantancoding]

Thanks 😊 , I’m glad that you understand it now!

[@maguilecutty]

How do you not have a million subs yet? Thanks heaps mate!

[@kantancoding]

Thanks! I’m glad you liked it 🙂

[@sp3ctrums264]

Thank you! Your video made it so much clearer!

[@kantancoding]

I’m really happy to hear that! 🙂

[@unizfrhn2803]

Wow bro. This is the best representation of this concept I've seen yet. Hats off.

[@kantancoding]

I’m glad to hear that! Thank you 🙏

[@charlesopuoro5295]

Thanks always for your clear explanations.

[@kantancoding]

Happy to help brother!

[@NattapongPUN]

You were so clearly explain. Thanks

[@suryak657]

Thanks for the video. It's been open unknown for me, you made it clear today. Thanks again !

[@kantancoding]

Awesome! I’m glad that it helped 😆

[@edenmeresman5619]

I dont know but some videos have the subtitles in spanish!! Thanks you soo much for this videos. Speacking too you a system engenieer student from Argentina.

[@kantancoding]

Hey! I’m glad they helped you 🙂

[@mrutyunjayarout3789]

You have explained it in the very nice way ...... belief me many pro cants explain the way u explained

[@kantancoding]

☺️ that’s great to hear. Thank you !

[@exheproject8362]

+1point in my test tomorrow with this, thnx^^

[@srinidhibandi2313]

Marvellous explaination!! HATS OFF

[@kantancoding]

Thanks! I’m glad it helped 😊

[@iamsaytara]

Brilliant video. Thanks for easing this out for me ❤️

[@kantancoding]

Of course! I’m glad it helped 😄

[@thurmansanders3072]

Terrific explanation thanks !

[@kantancoding]

Thanks for watching! 😊

[@teji_teji_]

Love this video so much. I though it was in base 10 this whole time like in regular math so I was so confused

[@kantancoding]

😂 yeah, seems like nobody really mentions that. I guess they think it’s obvious but it wasn’t obvious to me either when I was learning.

[@Jezonista]

Thank you for that video! Great explanation of the complicated concept!

[@kantancoding]

No problem! Happy to help 🙂

[@ashokyadavfqplmgxjia4668]

love you bro from India. it really helpful thanks to make this one....

[@kantancoding]

Thanks bro! Happy to help

[@Hurricane28110]

Excellently explained

[@msartist1767]

Thanks so much for these clear explanations. One thing I think would be helpful to cover are code examples of the space complexity as well as the time complexity.

[@Cos_Wayne]

This is a great explanation, thank you!

[@kantancoding]

Thank you! I’m glad it helped you 🙂

[@Marcus-cf2li]

Thank you bro. Your contents are absolutely useful for me. I am also interested in software design and I found it in your channel.

[@kantancoding]

No bro. Happy to help 🙂

[@9c_06_gedenararyaarunayoga2]

love from indonesia!!🔥🔥🔥

[@julietonyekaoha402]

Great explanation. Keep it coming

[@kantancoding]

Thank you very much! :) :)

[@Lobogrey2]

Explained this so clear for me thank you

[@kantancoding]

Awesome! I’m glad it helped 🙂

[@okeowoaderemi]

Christ it made so much sense now. Subscribed

[@kantancoding]

I’m glad it helped!

[@SRajalakshmiKsekar]

Excellent Explanation .Keep on going waiting for more videos in algorithm.

[@kantancoding]

Thank you! More algorithm videos on the way 😉

[@rar000000000]

Great video. in the Future, i would use "print(1), print(2), print(3)... etc" instead of 'log' when talking about logs.

[@kantancoding]

Haha I remember when I was making these videos I thought.. hmm hope they don’t get confused with log for logging to the console and log in big o.. too many 🪵

[@rar000000000]

@@kantancoding It wasn't too confusing, but I did have to rewind a couple times haha. I was relearning Django recently so my brain had to do a reset from pythons print() vs console.log()

[@RegularEverydayNormalGuy]

Instant subscribe man, the video is SO well done and easy to understand, it's amazing

[@kantancoding]

I’m glad to hear that! Thank you 🙏

[@mahamat_ali_youssouf]

Great explanation!

[@dylanngo4454]

Thank you so much, very interesting info.

[@kantancoding]

No problem! I’m glad you liked it 🙂

[@ben_jammin242]

Nice video. Maybe could bring up best and worse case complexity(ies) as well? The structuring of the video felt a little funny. Maybe it should just be a graphical/visual presentation with the voice overlay? Just an idea. Thanks for the vid!

[@MrDangerousBOB]

BRO THIS VIDEO IS AWESOME! Keep up the grind bro

[@kantancoding]

Thanks brother. I appreciate that! 🙏

[@robinmathur5807]

Explained very well with nice tool, great work and thanks

[@kantancoding]

Thank you 🙏 I’m glad it was helpful!

[@danielvandersand7789]

you best bet I'm about to like and subscribe. Thanks my man, going to be a great resource through my CS academic career

[@kantancoding]

Np! I’m glad it was helpful 🙏

[@akmalbukhariev7932]

it is worth to smash the like button bro. Thank you

[@kantancoding]

Thanks for the support brother!

[@volodymyrkredynets784]

I like your explanation, very understandable : )

[@kantancoding]

Thank you🙂 I’m happy to help

[@Babe_Chinwendum]

Thank you so much for the video

[@kantancoding]

My pleasure 🙂

[@aerospace_andy]

thank you, I understand it now!

[@kantancoding]

I’m glad🙂 keep it up!

[@HzHzHzHz111]

great explanation, one quick suggestion i have is add links to videos you're referring to in the video description (i.e logn explanation video) thanks!

[@kantancoding]

Good point. I will try to go through these videos and add the corresponding links. Thanks for the feedback!

[@zap7140]

Bro, Your video is helpful.

[@kantancoding]

Thanks! Happy to help brother 🙏

[@asmith7907]

These videos are amazing, good stuff

[@kantancoding]

Really happy to hear that! Thank you

[@planetofzakir971]

Great Explanation ❤

[@kantancoding]

I’m glad it helped you! 🙂

[@Gyooopp]

you got a new subscriber

[@kantancoding]

Welcome! 😊

[@bartek6100]

thx a lot man! helped so much, appreciate!

[@kantancoding]

Happy to help brother 🙂

[@mattp6460]

thank you very much

[@kantancoding]

Pleasure!

[@tavleenkaur8325]

THANK YOU SO MUCH!

[@kantancoding]

Of course! My pleasure 🙂

[@Dangerdog3000]

This was great dude, thank you

[@kantancoding]

No problem! I’m glad it helped 🙂

[@anaybaid]

This is soo helpful man!! :)

[@kantancoding]

Awesome! I’m happy to hear 🙂

[@anaybaid]

@@kantancoding Thanks! :)

[@amentothatt]

so well explained!

[@kantancoding]

Thank you!

[@jokesnerd9122]

Amazing stuff

[@kantancoding]

Thank you for your kind words 🙂

[@ashokyadavfqplmgxjia4668]

keep it up.........

[@Dhanushsaji]

Thank you

[@akmalbukhariev7932]

very good brother.

[@kantancoding]

Thank you 😊 I’m glad that it helps!

[@mammutti3000x]

thank you!

[@kantancoding]

My pleasure 😆

[@nquanta1548]

Got a new subscriber bro ,nice video👍❤️

[@kantancoding]

Thank you sir 🙏🙂

[@adilismail3593]

Thanks❤

[@kantancoding]

Happy to help ❤️

[@kostabakalinov1237]

very helpful!

[@kantancoding]

Thank you!

[@yebonbyun7648]

Thanks for super helpful video. I have one question. According to the previous videos, we consider the worst case or highest order part of the function. But what does it become O(n) times O(log n) instead of just O(n)? Thanks in advance!

[@kantancoding]

No problem! 😊 And to answer your question, it’s not just O(n). It’s O(n) at every level and there are log n levels 😉

[@penlavits3305]

didn't understand why exactly it works but i understand the math

[@hippohugz9966]

thankyou so much

[@kantancoding]

My pleasure! I’m happy to help 🙂

[@AwaraGhumakkad]

Its a very nice video but had one question anyone can answer - for the inner loop I believe complexity should have been - O(1), O(2), O(3) ........ and so on , then we can generalize that to O (n). instead here it has been shown as log(1), log(2) and so on ...... then generalization would be log(n). but log(n) is for out loop which is correct. please suggest

[@kantancoding]

Thank you!. Regarding your question, I think you are confusing the console.log() call in the visualization with the complexity.

[@anjildhamala4996]

@@kantancoding haha. That is super easy to be confused about especially since we are trying to understand logarithmic functions and every time you see log(x) you think logarithmic rather than shorthand notation for console.log.

[@kentsang9376]

omg thank you so much

[@kantancoding]

Happy to help 🙂

[@sagarghare9829]

Thanks, buddy for such the best videos. You explain very well. Are you of Indian origin?

[@kantancoding]

Hey thanks! I’m American 🙂

[@abldaz.]

Good video !

[@kantancoding]

Thank you! Thanks for watching 😊

[@hikamiawnyan]

Thanks man

[@kantancoding]

My pleasure 🙂

[@CROXoDyLE]

I really do enjoy this video and appreciate your work, but going forward I highly recommend reducing the amount of jittering in the animations it was a bit distracting.

[@kantancoding]

😂🤣 yeah, unfortunately the software I used was pretty 🗑 so I couldn’t remove the jittering 🤷‍♂️

[@aat501]

@@kantancoding I thought it was fine. thanks for the video

[@Danfin123]

thank you brooo!!!!!!1

[@kantancoding]

Any time brother 😊

[@iamthatsid]

Thanks bro !

[@kantancoding]

My pleasure brother😆

[@sou3598]

thanks a lot for your video. Was wondering how a merge sort is actually O(n log n) ? I mean for dividing is O(n log n) so the other n is for comparing elements ? How’s that ?

[@kantancoding]

Hey, to understand this, try to think about a simpler problem, merging two sorted lists. merging two sorted lists is O(n+m) where n and m are the sizes of the two sorted lists. So we need to touch every element in both n and m to merge them and maintain the sort. Now think about what we are doing at every level with merge sort. We are merging at most n sorted lists (the bottom most level) and at every level, regardless of the number of sorted lists we are merging, the total number of elements in all of the lists on that level is n. So we need to touch n elements at every level. There are log n levels so complexity is O(n * log n)

[@MrSunmorning]

Can you do some run time comparison between merge sort and fibonacci? Given that merge sort split the input in halves on each level of recursion, so we will have nlog(n) run time. When I draw out the recursion calls (like a tree structure), I see that fib look quite similar to merge sort, but fib run time will be 2^n. I think because the input size of the fib recursion calls not reducing so fib is not going to be a log run time. However, I still have hard time wrapping my head around this.

[@kantancoding]

There’s already a video in this series that explains Fibonacci time/space complexity 👍

[@mohammedalgaradi8661]

great tutorial, what software you use to make the presentation ?

[@kantancoding]

I actually don't remember the name of the software that I used for this. I remember I googled "best whiteboard animation software" or something like that and just picked the one with the best ratings 😎

[@anjildhamala4996]

So, this is pretty obvious when one specifies a value to n (preferably small) and then evaluate how many times it is ran. Is there any pitfall to this approach?

[@Mr_TheMan]

thx

[@kantancoding]

No problem!

[@magzhanabdibayev3818]

Great video. A short and understandable explanation.

[@kantancoding]

Thank you! I’m glad that you liked it 😆

[@bhupendra8429]

Can you explain about O(n*m),O(n+m) something like that, I have seen this O in leet code time complexity test

[@kantancoding]

They are probably just using n and m to represent two different inputs. This video might help you understand what I mean kzbin.info/www/bejne/qHmwZK2NnNODjKM

[@FitnessChaos]

Good vid mate

[@kantancoding]

Thank you! I’m glad it helped 😆

[@ninadpradhan6566]

What tool did u use to create this transparent white board video ? Any information is appreciated

[@kantancoding]

I think you can just google "best whiteboard animation software." That should put you on the right track.

[@ninadpradhan6566]

@@kantancoding thanks man

[@sameerroshan9542]

O (log N) works for this example but O(n/2) also works for the top level loop which makes it O(n) soo how do you pick log here??

[@kantancoding]

I’m sorry but I don’t understand what you mean. I explain why it’s O(n log n) in the video. Which part specifically is confusing you?

[@sameerroshan9542]

@@kantancoding The top loop is O(log N). But it can also be O(N/2) right? if not, why can't it be O(N/2) ?

[@ProvakorKonik]

Awesome............ Subscribing to you...

[@kantancoding]

Thank you! I’m glad it helped!

[@JuanGarcia-dg8zc]

so its log n complexity because instead of going through full size of input n we're cutting it in half?? just wanna clarify!!!

[@kantancoding]

Hmm not really. This is n log n. I suggest watching the entire series 🙂

[@loganhawkins6486]

How do you find the time complexity of O(nlogn)

[@goldentitan311]

nice

[@kantancoding]

Thank you 🙂

[@r20de20]

3:22 "Log is always the base of 2". Oh come on! Why does every field have different notation? "Log x" in standard math means base 10, "Log x" in WolframAlpha means natural log, so base e, and now in the computer science there's a base of 2? I mean, yeah, seems logical, because binary... however the lack of unification is horrifying ;-; you can never be sure, if you see just an equation. But anyway! Good video, learnt a lot! :D

[@kantancoding]

😂🤣 Thank you! I understand your frustration

[@BBTALKZ]

So if there’s a while loop and a for loop would that be a n log n then?

[@kantancoding]

Not necessarily. Depends on the algorithm. A while loop can be an infinite loop. What is the for loop iterating on? You have to diagnose each algorithm individually. Don’t make the mistake of assuming the complexity of an algorithm based on surface level things like the number for nested loops or whatever. Really look at the input and see how it is scaling.