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

Big O Notation Series #5: O(n log n) explained for beginners: In this video I break down O(n log n) into tiny pieces and make it understandable for beginners. Algorithm complexity O(n log n).
More from this series: • Big O For Software Eng...
on log n explained for beginners big o notation time complexity log n big o notation explained big o big o notation tutorial time complexity tutorial big oh o(log n) time complexity explained big o series big o mini series big o notation series big o notation mini series Join the Discord to talk to me and the rest of the community!
/ discord

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

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

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

[@techdan7098]

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?

[@techdan7098]

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

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

[@techdan7098]

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

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

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

[@sp3ctrums264]

Thank you! Your video made it so much clearer!

[@kantancoding]

I’m really happy to hear that! 🙂

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

[@shubhanshusahuu]

Best video to understand n log n

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

[@NattapongPUN]

You were so clearly explain. Thanks

[@srinidhibandi2313]

Marvellous explaination!! HATS OFF

[@kantancoding]

Thanks! I’m glad it helped 😊

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

[@JamieDawsonCodes]

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

[@kantancoding]

Awesome! Glad it helped you out 😎

[@iamsaytara]

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

[@kantancoding]

Of course! I’m glad it helped 😄

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

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

[@mahamat_ali_youssouf]

Great explanation!

[@9c_06_gedenararyaarunayoga2]

love from indonesia!!🔥🔥🔥

[@amentothatt]

so well explained!

[@kantancoding]

Thank you!

[@Jezonista]

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

[@kantancoding]

No problem! Happy to help 🙂

[@Hurricane28110]

Excellently explained

[@Cos_Wayne]

This is a great explanation, thank you!

[@kantancoding]

Thank you! I’m glad it helped you 🙂

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

[@mammutti3000x]

thank you!

[@kantancoding]

My pleasure 😆

[@bartek6100]

thx a lot man! helped so much, appreciate!

[@kantancoding]

Happy to help brother 🙂

[@lillyput2275]

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

[@kantancoding]

Happy to help 🙂

[@ashokyadavfqplmgxjia4668]

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

[@kantancoding]

Thanks bro! Happy to help

[@robinmathur5807]

Explained very well with nice tool, great work and thanks

[@kantancoding]

Thank you 🙏 I’m glad it was helpful!

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

[@dylanngo4454]

Thank you so much, very interesting info.

[@kantancoding]

No problem! I’m glad you liked it 🙂

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

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

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

[@zap7140]

Bro, Your video is helpful.

[@kantancoding]

Thanks! Happy to help brother 🙏

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

[@aerospace_andy]

thank you, I understand it now!

[@kantancoding]

I’m glad🙂 keep it up!

[@maguilecutty]

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

[@kantancoding]

Thanks! I’m glad you liked it 🙂

[@asmith7907]

These videos are amazing, good stuff

[@kantancoding]

Really happy to hear that! Thank you

[@julietonyekaoha402]

Great explanation. Keep it coming

[@kantancoding]

Thank you very much! :) :)

[@adilismail3593]

Thanks❤

[@kantancoding]

Happy to help ❤️

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

[@exheproject8362]

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

[@Dhanushsaji]

Thank you

[@Babe_Chinwendum]

Thank you so much for the video

[@kantancoding]

My pleasure 🙂

[@Lobogrey2]

Explained this so clear for me thank you

[@kantancoding]

Awesome! I’m glad it helped 🙂

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

[@abldaz.]

Good video !

[@kantancoding]

Thank you! Thanks for watching 😊

[@planetofzakir971]

Great Explanation ❤

[@kantancoding]

I’m glad it helped you! 🙂

[@okeowoaderemi]

Christ it made so much sense now. Subscribed

[@kantancoding]

I’m glad it helped!

[@Gyooopp]

you got a new subscriber

[@kantancoding]

Welcome! 😊

[@eleandro]

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

[@kantancoding]

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

[@akmalbukhariev7932]

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

[@kantancoding]

Thanks for the support brother!

[@ashokyadavfqplmgxjia4668]

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

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

[@volodymyrkredynets784]

I like your explanation, very understandable : )

[@kantancoding]

Thank you🙂 I’m happy to help

[@MrDangerousBOB]

BRO THIS VIDEO IS AWESOME! Keep up the grind bro

[@kantancoding]

Thanks brother. I appreciate that! 🙏

[@SRajalakshmiKsekar]

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

[@kantancoding]

Thank you! More algorithm videos on the way 😉

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

[@nquanta1548]

Got a new subscriber bro ,nice video👍❤️

[@kantancoding]

Thank you sir 🙏🙂

[@akmalbukhariev7932]

very good brother.

[@kantancoding]

Thank you 😊 I’m glad that it helps!

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

[@jokesnerd9122]

Amazing stuff

[@kantancoding]

Thank you for your kind words 🙂

[@kostabakalinov1237]

very helpful!

[@kantancoding]

Thank you!

[@Danfin123]

thank you brooo!!!!!!1

[@kantancoding]

Any time brother 😊

[@kentsang9376]

omg thank you so much

[@kantancoding]

Happy to help 🙂

[@hippohugz9966]

thankyou so much

[@kantancoding]

My pleasure! I’m happy to help 🙂

[@anaybaid]

This is soo helpful man!! :)

[@kantancoding]

Awesome! I’m happy to hear 🙂

[@anaybaid]

@@kantancoding Thanks! :)

[@hikaru8453]

Thanks man

[@kantancoding]

My pleasure 🙂

[@Mr_TheMan]

thx

[@kantancoding]

No problem!

[@iamthatsid]

Thanks bro !

[@kantancoding]

My pleasure brother😆

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

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

[@FitnessChaos]

Good vid mate

[@kantancoding]

Thank you! I’m glad it helped 😆

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

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

[@ProvakorKonik]

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

[@kantancoding]

Thank you! I’m glad it helped!

[@loganhawkins6486]

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

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

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

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

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

[@OmarAli-nf2yw]

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.

[@magzhanabdibayev3818]

Great video. A short and understandable explanation.

[@kantancoding]

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

[@sagarghare9829]

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

[@kantancoding]

Hey thanks! I’m American 🙂

[@penlavits3305]

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

[@ColinLast]

would a while loop inside a for loop also be O(n log n)?

[@kantancoding]

It depends on the algorithm. I suggest watching the entire series to get a better understanding 🙂

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

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

[@goldentitan311]

nice

[@kantancoding]

Thank you 🙂

[@dinul117]

i found this to be a good explanation, if you have time maybe show an example with merge sort as it is also O(n*log(n)). I watched another video on it and it confused me. subscribed :)

[@kantancoding]

Hello! Thank you! and actually, this series has a couple of videos on merge sort. Here's one of them kzbin.info/www/bejne/fqOmgaSAfbaGrrs 😄

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

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

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

[@ehsanafzal1589]

Hello dear Im student of cs We are studying analysis of algorithm... How i can get good understanding... And where i can get questions.. For better preparation

[@ehsanafzal1589]

Tell me guidelines

[@kantancoding]

Hello! I have an entire playlist on this here: kzbin.info/aero/PL7g1jYj15RUPVZDU9C276SZvlJjf4hzqV And if you have any specific questions or would like me to cover something, feel free to ask! I would love to help you out :)

[@kantancoding]

@@ehsanafzal1589 You can just watch the playlist from start to finish. It goes in order of difficulty for the most part.

[@ehsanafzal1589]

@@kantancoding it will be very grateful if you share me some questions or any other material related to this subject or any website where i learn and polish my skills of algorithm

[@kantancoding]

@@ehsanafzal1589 It really depends on what you want to focus on specifically. Are you only trying to learn how to analyze algorithms? Or are you looking to learn how to produce your own algorithms? There are really good resources online like hackerrank and leetcode if you are looking to become more comfortable with algorithms in general. Both of those sites have hundreds of questions if that is what you are looking for. Also, if you are interested in books, I can recommend some but I would need to know what you are trying to learn specifically.

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