Introduces asymptotic bounds and proves that comparison sorting requires Ω(N log N) time in the worst case. Covers the decision-tree argument and examples illustrating the sorting lower bound.
Save to open this file
Berkeley CS 61B: Data Structures
All
01-Welcome to 61B, Intro to Java
- 01-Welcome to 61B, Intro to Java
- 02-Defining and Using Classes, Lists
- 03-Lists, Arrays, Maps, References
- 04-Testing
- 05-Packages, Recursion, IntLists
- 06-SLLists, Nested Classes, Sentinel Nodes
- 07-DLLists, Basic ALists
- 08-Resizing and Circular Arrays
- 09-Interface and Implementation Inheritance
- 10-Iterators, Iterables, and Equals
- 11-Subtype Polymorphism, Comparables, Comparators
- 12-Review, Midterm Practice
- 13-Asymptotics I
- 14-Disjoint Sets
- 15-Asymptotics II
- 16-Asymptotics III
- 17-Sets, Extends, and BSTs
- 18-B-Trees
- 19-Red-Black Trees
- 20-Heaps, Priority Queues, and Tree Representations
- 21-Tree and Graph Traversals
- 22-Graph Traversals and Implementations
- 23-Shortest Paths
- 24-Minimum Spanning Trees
- 25-Directed Acyclic Graphs
- 26-Hashing I
- 27-Hashing II
- 28-Tries
- 29-Software Engineering I
- 31-Software Engineering II - BYOW Warmup
- 32-Basic Sorts
- 33-Insertion Sort and Intro to Quicksort
- 34-Quicksort
- 35-Sorting and Algorithmic Bounds
- 36-Radix Sorts
- 37-The Social Implications of Computing
- 38-Software Engineering III - AI in Software Engineering
- 39-Compression
- 40-Summary, Fun