Complexity Analysis & Big-O Notation

61 lessons in Data Structures, Algorithms

• Big-Omega NotationFlashcard
• Linearithmic Time O(n log n)Flashcard
• Quadratic Time O(n^2)Quiz
• Sequential Code BlocksQuiz
• Constant Time O(1)Quiz
• Linear Time O(n)Quiz
• Logarithmic Time O(log n)Quiz
• Linearithmic Time O(n log n)Quiz
• Exponential Time O(2^n)Quiz
• Ordering Complexity ClassesQuiz
• Counting Basic OperationsQuiz
• Dropping ConstantsQuiz
• Dropping Lower-Order TermsQuiz
• Complexity of a Single LoopQuiz
• Complexity of Nested LoopsQuiz
• Input Size Drives ComplexityQuiz
• How Runtime ScalesQuiz
• What Complexity Analysis Is and Why It MattersSlides / Video
• Using Complexity to Compare AlgorithmsSlides / Video
• Best, Average, and Worst CaseSlides / Video
• Space Complexity BasicsSlides / Video
• Analyzing Nested Loops for Time ComplexitySlides / Video
• Analyzing Simple Loops for Time ComplexitySlides / Video
• Dropping Constants and Lower-Order TermsSlides / Video
• Ranking Common Complexity ClassesSlides / Video
• Sort Then Loop ComplexityCode Quiz
• Halving Loop Logarithmic TimeCode Quiz
• Nested Loops Quadratic TimeCode Quiz
• Constant Time Array AccessCode Quiz
• Single Loop Linear TimeCode Quiz
• Loop With Doubling StepCode Quiz
• Worst Case Of Linear SearchCode Quiz
• Space Complexity Of CopyCode Quiz
• Two Input VariablesCode Quiz
• Summing Sequential LoopsCode Quiz
• Ordering Growth RatesCode Quiz
• Dropping Constants In Big-OCode Quiz
• Common Big-O Complexity ClassesSlides / Video
• Big-O as an Upper BoundSlides / Video
• Definition and Intuition of Big-O NotationSlides / Video
• Logarithmic Time O(log n)Flashcard
• Quadratic Time O(n^2)Flashcard
• Dropping Lower-Order TermsFlashcard
• Complexity of Nested LoopsFlashcard
• Auxiliary Space vs Total SpaceFlashcard
• Factorial Time O(n!)Flashcard
• Best, Average, and Worst CaseFlashcard
• Dropping Constants in Big-OFlashcard
• Comparing Growth RatesFlashcard
• Sequential Statements (Addition)Flashcard
• Big-Theta NotationFlashcard
• Why We Focus on Worst CaseFlashcard
• Big-O Formal Notation and MeaningFlashcard
• Linear Time O(n)Flashcard
• Counting OperationsFlashcard
• Constant Time O(1)Flashcard
• Complexity of Single LoopsFlashcard
• Exponential Time O(2^n)Flashcard
• How Runtime Grows as Input GrowsSlides / Video
• Input Size n: The Basis of AnalysisSlides / Video
• Counting Operations to Estimate CostSlides / Video