69 items
Finding 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
FlashcardLinearithmic Time O(n log n)
FlashcardBig-Omega Notation
FlashcardExponential Time O(2^n)
QuizOrdering Complexity Classes
QuizCounting Basic Operations
QuizDropping Constants
QuizDropping Lower-Order Terms
QuizComplexity of a Single Loop
QuizComplexity of Nested Loops
QuizInput Size Drives Complexity
QuizHow Runtime Scales
QuizSequential Code Blocks
QuizConstant Time O(1)
QuizLogarithmic Time O(log n)
QuizLinear Time O(n)
QuizQuadratic Time O(n^2)
QuizLinearithmic Time O(n log n)
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 / VideoLoop With Doubling Step
Code QuizNested Loops Quadratic Time
Code QuizSingle Loop Linear Time
Code QuizConstant Time Array Access
Code QuizOrdering Growth Rates
Code QuizHalving Loop Logarithmic Time
Code QuizSort Then Loop Complexity
Code QuizDropping Constants In Big-O
Code QuizSumming Sequential Loops
Code QuizTwo Input Variables
Code QuizSpace Complexity Of Copy
Code QuizWorst Case Of Linear Search
Code QuizCommon Big-O Complexity Classes
Slides / VideoBig-O as an Upper Bound
Slides / VideoDefinition and Intuition of Big-O Notation
Slides / VideoComplexity of Single Loops
FlashcardComparing Growth Rates
FlashcardSequential Statements (Addition)
FlashcardLinear Time O(n)
FlashcardCounting Operations
FlashcardExponential Time O(2^n)
FlashcardConstant Time O(1)
FlashcardLogarithmic Time O(log n)
FlashcardBig-Theta Notation
FlashcardDropping Constants in Big-O
FlashcardBest, Average, and Worst Case
FlashcardFactorial Time O(n!)
FlashcardAuxiliary Space vs Total Space
FlashcardComplexity of Nested Loops
FlashcardDropping Lower-Order Terms
FlashcardQuadratic Time O(n^2)
FlashcardWhy We Focus on Worst Case
FlashcardBig-O Formal Notation and Meaning
FlashcardHow Runtime Grows as Input Grows
Slides / VideoInput Size n: The Basis of Analysis
Slides / VideoCounting Operations to Estimate Cost
Slides / VideoFinding Duplicates and Big-O
Spot the bug that quietly turns an intended O(n) duplicate check into O(n squared).
// Goal: return true if array has any duplicate, in O(n) time and O(n) space
function hasDuplicate(arr) {
const seen = [];
for (let i = 0; i < arr.length; i++) {
if (seen.includes(arr[i])) {
return true;
}
seen.push(arr[i]);
}
return false;
}The function returns correct results, but fails its stated O(n) time requirement. What is the bug?