Time and Space Complexity COMPLETE Tutorial - What is Big O?

This tutorial will help you go from beginner to advanced with “Time and Space Complexity Analysis”.

- We cover in-depth explanations of Big-O, Big-Omega, Theta and other notations
- Types of recurrence relations (Linear, Divide-and-Conquer)
- How to solve any relation easily
- Time and space complexity of recursive programs
- The maths along with explaining it in a simple language
- Comparisons of various complexities along with graphs
- NP-Completeness introduction
- and much more!

NOTE: If you get any root in the recurrence relation equation, just replace N as 2^k. This will now be converted to divide and conquer relation. Then solve normally using Akra-Bazzi formula and in the end substitute for N.

Take part in the learning in public initiative! Share your learnings on LinkedIn and Twitter with #DSAwithKunal & don't forget to tag us!

👉 Resources

=========================================
Timestamps:
00:00:00 Introduction
00:03:45 Example
00:06:27 Time Complexity
00:17:18 Comparing Complexities
00:23:18 Procedure for Analysing Complexity
00:37:50 Big-Oh Notation
00:44:38 Big-Omega Notation
00:46:28 Big-Theta Notation
00:49:20 Little-Oh Notation
00:53:03 Little-Omega Notation
00:55:29 Space Complexity
00:58:22 Question
01:04:24 Complexity Analysis : Sorting Algorithms
01:05:57 Complexity Analysis : Recursive Programs
01:13:55 Types of Recurrence Relations
01:16:49 Divide-and-Conquer Recurrence Relation
01:25:55 Akra-Bazzi Theorem
01:44:11 Linear Recurrence Relation
01:46:46 Solving Homogenous Linear Recurrence Relation
01:57:43 Q : Find nth Fibonacci Number using Golden ratio
02:03:15 Q : Solve Recurrence Relation with Repeated Roots
02:08:00 Non-Homogeneous Linear Recurrence Relation
02:09:10 Solving Non-Homogenous Linear Recurrence Relation
02:16:28 How to guess a Particular Solution?
02:20:34 Example
02:24:54 NP-Complete Problems
02:27:20 Outro

#complexity #placement #dsa #interviews

[shofiyabootwala]

Never learnt Time and Space complexity so profoundly. Immensely grateful. Thank You.

[Code_Hacks_Learning]

Who are watching 2024 for placements . Tq kunal❤

[rajattiwari]

Everyone has "Jeetu bhaiya"in their life.
My Jeetu bhaiya is Kunal
I am so happy to found out your Dsa bootcamp.
"koi subject itna hard nhi lagta agr teacher sahi ho to"
Thanks Kunal

[sujalsamai]

On other channel's video, even 20 minutes feel like eternal, but here I'm watching your videos for 2 hours and it feels like 10 minutes only. You truly made things so interesting, that it feels I'm giving my time in right things!!💙

[mansipandey]

Kunal I can say your course is helping even experienced guys as well to prepare and get better at their work. And yes no YouTube channel is giving this content for free.

[adityaraj_]

Hey Kunal, I've been following all your DSA videos from the beginning and I'm actually learning much better than ever. Thanks for your efforts!

[Eagle.k]

638K views and only 17k likes, guys this is not worth it. best DSA playlist on YT, let others take benefit of it. YouTube algorithm will rank up this video if you like it.👍🏻👍🏻

[ashutoshrudraksh]

Honestly, I never tried to skip or got bored. His way of entangling with details and being succinct at the same time is rare.
Thank you!
we all, appreciate your hard work!

[bindubeesetti]

Dear SEO, don't do any kind of logic. just check if the user entered dsa in the youtube search box, then Kunal Kushwaha's playlist should come first. Thank you so much Kunal. you are really really doing a great job. its an act of real kindness(sharing what the real wealth of knowledge is there in you)

[veeee]

this course is so much in depth of space and time complexity you can never this level of knowledge anywhere, i had a hard time getting it just because maths is my weak point but its very detailed explanation .

[rohanmhadgut]

I have completed my engineering last year and till today I used to think time complexity = Time taken, but today I understood that time complexity is a function that gives the relationship between how time grows with growth in input. Thanks for this video brother 🙏. It was amazing 👏 🙌 ❤

[MrVrtex]

The only channel where I never skip in a video. Every second is an important Information.... You can't guess when he will say something so valuable that might shock your interviewer.

[manyagupta]

This is my third time watching a video on time complexity. The previous ones were highly recommended and famous but this is on another level. Never have I ever been able to solve these relations this easily.

[amardeepyadav]

The akra bazzi formula and getting the formula for the Fibonacci number is amazing, I don't think anyone on youtube has ever made this kind of video.

[ranitaghosh]

Best time complexity video (not only in youtube).Everything is explained from root. Best thing is every part is explained in detail. I am very happy I don't have to see any video further for time complexity or any dsa related topic. Infact the sorting videos are good. Kunal gives best best best content. Looking forward for more tutorials.

[_PiyushKumar-vvui]

I am so much amazed right now, paused the video at 2:01:37, this is THE BEST I repeat THE BEST DSA course. We are blessed to have a educator like you. I really really appreciate your efforts. YOU ARE THE BEST

[nabhagmotivaras]

To be Very Honest: I think this course Doesn't Just Covers DSA but instead it covers. : DSA + Design and Analysis of Algorithms + Use of Discreate Mathematics. (Dont trust me. Compare Commclassroom Syllabus with Top Colleges Syllabus of DAA and DSA.) And if You are Tier 3 Guy like me, I am Sure these subject would get very very very Easy for you and Most of the time you will give Exams of this subject without any prior exam preparation.

[nileshnaik]

Hey Kunal I have just completed time complexity and space complexity lecture of your playlist, I have been watching the series from start the approach in which u are teaching is amazing.Tried various courses but I felt they complicated simple things and I left after some time but your course is truly amazing whenever faced any difficulty I rewatch that particular part👍❤️❤️keep uploading such amazing stuff

[akshatpandey]

I am masters student at Iit(ism) dhanbad and i can assure you, his way of teaching and clearing doubts is better than most of my prof.
My prof. just taught time complexity for 1 lecture and just mumbled some words notation and that was it!He moved on!!
For rest of the topic my prof. was amazing.He has a unique way of teaching algo and then having a lab where it is discussed, but this topic got left out and i was unable to understand it.
My prof himself told to search for things online and it is best to learn yourself then relying everything on teacher and he is 100% correct.My clg and prof. Are amazing but many tier 3 college don't have such good prof.
So there is need of such amazing people as Kunal who are willing to have a change!!

[legendrandom]

A very great and profound lecture on time complexity I highly appreciate your efforts...Thank you so much !!..Although I want to add some things if someone is still having doubts in getting the complexity from the akra bazzi or the techniques mention above I highly suggest you guys to look at master theorem, substitution and other methods too they are good too and easy, after understanding them things become easy and you will understand the formulas in this lecture more easily ...after that you can choose which method is best for you and keep going with that!
In the end Just Work Smart(always know which things to mainly focus on and rest improvise)
Keep learning and Keep going !!