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