Video Description

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 - Join Replit: http://join.replit.com/kunal-kushwaha - Complete Java DSA playlist: https://www.youtube.com/playlist?list=PL9gnSGHSqcnr_DxHsP7AW9ftq0AtAyYqJ - Code, Assignments, & Notes: https://github.com/kunal-kushwaha/DSA-Bootcamp-Java ➡️ Connect with me: https://www.techwithkunal.com ========================================= 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