85 items
Reductions and Lower Bounds Direction
QuizThe Hash-Set Trade-off That Wasn't
Code QuizComplexity Trade-offs & Problem Reduction
Slides / VideoComplexity Trade-offs & Problem Reduction
FlashcardDuplicate Check with a Set
Code QuizTwo-Sum Time/Space Trade-off Analysis
QuizBig-O Trade-offs in Real Code
Slides / VideoTrading Space for Time with Memoization
FlashcardHidden Quadratic Complexity Bug
Code QuizAmortized Complexity of Dynamic Array Append
QuizUnderstanding Big-O Notation
QuizClaimed O(n) Sum of Uniques
Code QuizBroken Memoization in Fibonacci
Code QuizBig-O Time/Space Trade-offs
QuizBig-O Time & Space Trade-offs
Slides / VideoTime/Space Trade-offs in Big-O Analysis
FlashcardFinding Duplicates and Big-O
Code QuizNested Loop Time & Space Complexity
QuizOff-by-One in Duplicate Check
Code QuizBig-O of a Simple Loop
QuizBig-O Notation Basics
Slides / VideoBig-O Notation Basics
FlashcardBig-O for Time and Space
Slides / VideoBig-O Time & Space Basics
FlashcardBig-Omega Notation
FlashcardLinearithmic Time O(n log n)
FlashcardConstant Time O(1)
QuizLinearithmic Time O(n log n)
QuizCounting Basic Operations
QuizExponential Time O(2^n)
QuizComplexity of a Single Loop
QuizQuadratic Time O(n^2)
QuizSequential Code Blocks
QuizDropping Constants
QuizOrdering Complexity Classes
QuizHow Runtime Scales
QuizInput Size Drives Complexity
QuizLogarithmic Time O(log n)
QuizDropping Lower-Order Terms
QuizLinear Time O(n)
QuizComplexity of Nested Loops
QuizWhat Complexity Analysis Is and Why It Matters
Slides / VideoUsing Complexity to Compare Algorithms
Slides / VideoBest, Average, and Worst Case
Slides / VideoSpace Complexity Basics
Slides / VideoAnalyzing Nested Loops for Time Complexity
Slides / VideoAnalyzing Simple Loops for Time Complexity
Slides / VideoDropping Constants and Lower-Order Terms
Slides / VideoRanking Common Complexity Classes
Slides / VideoSingle Loop Linear Time
Code QuizWorst Case Of Linear Search
Code QuizSpace Complexity Of Copy
Code QuizDropping Constants In Big-O
Code QuizHalving Loop Logarithmic Time
Code QuizConstant Time Array Access
Code QuizTwo Input Variables
Code QuizNested Loops Quadratic Time
Code QuizSort Then Loop Complexity
Code QuizSumming Sequential Loops
Code QuizOrdering Growth Rates
Code QuizLoop With Doubling Step
Code QuizCommon Big-O Complexity Classes
Slides / VideoBig-O as an Upper Bound
Slides / VideoDefinition and Intuition of Big-O Notation
Slides / VideoComplexity of Nested Loops
FlashcardFactorial Time O(n!)
FlashcardWhy We Focus on Worst Case
FlashcardBig-Theta Notation
FlashcardLogarithmic Time O(log n)
FlashcardDropping Lower-Order Terms
FlashcardDropping Constants in Big-O
FlashcardComplexity of Single Loops
FlashcardCounting Operations
FlashcardLinear Time O(n)
FlashcardQuadratic Time O(n^2)
FlashcardBig-O Formal Notation and Meaning
FlashcardConstant Time O(1)
FlashcardExponential Time O(2^n)
FlashcardAuxiliary Space vs Total Space
FlashcardSequential Statements (Addition)
FlashcardBest, Average, and Worst Case
FlashcardComparing Growth Rates
FlashcardHow Runtime Grows as Input Grows
Slides / VideoInput Size n: The Basis of Analysis
Slides / VideoCounting Operations to Estimate Cost
Slides / VideoNested Loop Time & Space Complexity
Analyze the time and space complexity of a function that builds a 2D matrix using nested loops.
A function takes an array of size n and creates an n x n matrix, filling each cell by summing a pair of elements. What are its time and space complexities?