This lesson includes an expert video walkthrough — purchase once for a full year of unlimited replays to master every key point 🎬
Algorithm Basics
Knowledge Summary
What Is an Algorithm
An algorithm is a sequence of well-defined steps for solving a specific problem. The five major properties of an algorithm are:
- Finiteness: the algorithm must terminate after a finite number of steps
- Definiteness: each step must have a clear and unambiguous definition
- Effectiveness: each step can be carried out through a finite number of basic operations
- Input: it has zero or more inputs
- Output: it has one or more outputs
Time Complexity
Big-O notation is used to describe the relationship between an algorithm's running time and the input size.
Common complexities, from fast to slow:
Space Complexity
A measure of how much temporary storage space an algorithm uses during execution.
Common Algorithmic Ideas
| Algorithmic Idea | Core Approach | Typical Applications |
|---|---|---|
| Enumeration | Try all possibilities one by one | Password cracking, simple search |
| Greedy | Take the locally optimal choice at each step | Activity scheduling, coin change |
| Divide and Conquer | Divide -> solve -> combine | Merge sort, quick sort |
| Recurrence / Recursion | Use solutions to subproblems | Fibonacci, factorial |
| Search | Traverse the state space with DFS/BFS | Maze problems |
| Dynamic Programming | Avoid repeated computation with memorization | Knapsack problems |
Comparison of Sorting Algorithms
| Algorithm | Average Time | Worst Time | Space | Stability |
|---|---|---|---|---|
| Bubble Sort | O(n²) | O(n²) | O(1) | Stable |
| Selection Sort | O(n²) | O(n²) | O(1) | Unstable |
| Insertion Sort | O(n²) | O(n²) | O(1) | Stable |
| Merge Sort | O(n log n) | O(n log n) | O(n) | Stable |
| Quick Sort | O(n log n) | O(n²) | O(log n) | Unstable |
| Counting Sort | O(n+k) | O(n+k) | O(k) | Stable |