Concept
Average-case complexity
Related lectures (53)
Complexity & Induction: Algorithms & Proofs
Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.
Discussion of Complexity
Explores worst-case complexity in computer science and the importance of real-life complexity in algorithm selection.
Linear Algebra: Efficiency and Complexity
Explores constraints, efficiency, and complexity in linear algebra, emphasizing convexity and worst-case complexity in algorithm analysis.
Divide-and-Conquer: Merge Sort
Explores loop invariants, time analysis, and the Divide-and-Conquer approach with a focus on Merge Sort.
Algorithmic Complexity: Theta Notation
Explores algorithmic complexity, comparing growth rates using Theta notation and characterizing different complexity classes.
Optimization Algorithms
Covers optimization algorithms, convergence properties, and time complexity of sequences and functions.
Algorithmic Complexity: Definition and Examples
Explores algorithm correctness, worst-case complexity analysis, and efficiency comparison based on input size.
Shor Algorithm: Quantum Factorization
Covers the Shor algorithm for quantum factorization and the general formula for arithmetic periods.
Search Algorithms: Dichotomy Search
Explores dichotomy search algorithms, analyzing complexity and implementation details for efficient searching in sorted lists.
Low Complexity MIMO ML Receivers
Explores MIMO spatial multiplexing, ML detection, receivers with fading, tree representation, and sphere decoding.