CS50 Fall 2025 - Lecture 3 - Algorithms (live, unedited)

Overview

CS50's Lecture 3 introduces fundamental algorithms, starting with a human-powered attendance count demonstrating linear and logarithmic time complexity. The lecture then delves into linear search (O(n)) and binary search (O(log n)) using "lockers" and "money" as metaphors, before explaining Big O notation for analyzing algorithm efficiency. It also covers selection sort, bubble sort (both O(n^2)), and the more efficient merge sort (O(n log n)), highlighting recursion as a powerful technique for solving complex problems like drawing Mario pyramids.

Key takeaways

Algorithms like linear search (O(n)) and binary search (O(log n)) have different efficiencies based on problem size.
Big O notation (O(n), O(log n), O(n^2), O(n log n)) provides a standardized way to describe algorithm performance.
Selection sort and bubble sort are simple but inefficient O(n^2) algorithms.
Merge sort, using a divide-and-conquer strategy, achieves efficient O(n log n) performance.
Recursion is a powerful technique where a function calls itself, breaking problems into smaller, self-similar subproblems with a base case.
Data structures like arrays and structs (e.g., `person`) organize data, impacting algorithm design and efficiency.

Chapters

17:48 Introduction to Algorithms and Time Complexity

Algorithms are step-by-step instructions for solving problems.
Sorting orders information from smallest to largest or alphabetically.
Counting attendance manually (1, 2, 3...) is O(n) complexity.
Counting by 2s is faster but still linear, O(n).

20:30 Human-Powered Attendance Algorithm

Participants stand, pair off, sum numbers, and one sits down.
This process repeats, demonstrating a divide-and-conquer approach.
The final count aggregates all initial '1's, theoretically representing total attendance.

26:20 Analyzing Algorithm Efficiency: Linear vs. Logarithmic Growth

Counting one by one (1, 2, 3...) is linear (straight line graph).
Counting by 2s (2, 4, 6...) is also linear but faster (steeper line).
The human-powered attendance algorithm's time grows very slowly (logarithmic), requiring few steps even with many participants.

28:40 Understanding Arrays and Memory Access

Arrays store data contiguously in memory, like back-to-back lockers.
Computers access memory sequentially, one location at a time.
Memory locations are zero-indexed (locker 0, locker 1, etc.).

34:50 Linear Search: Finding a $50 Bill

Jose demonstrates linear search by checking each locker (door) sequentially.
The algorithm checks every item until the target is found.
This is O(n) in the worst case, as it might check all items.

35:20 Binary Search: Leveraging Sorted Data

Caitlin uses binary search on sorted "lockers" (money denominations).
The strategy is to check the middle element and eliminate half the search space.
This requires the data to be sorted beforehand.

37:15 Pseudocode for Linear Search

Iterates through each element (door) from left to right.
Returns 'true' if the target (50) is found.
Returns 'false' if the entire array is searched without finding the target.

38:30 Pseudocode for Binary Search

Checks the middle element.
If target is smaller, recursively searches the left half.
If target is larger, recursively searches the right half.
Includes a base case to return 'false' if no elements are left.

44:20 Big O Notation: Analyzing Running Time

Linear search is O(n) (on the order of n steps).
Binary search is O(log n) (on the order of log base 2 of n steps).
Big O notation focuses on the dominant term as problem size (n) grows.
Lower-order terms and constants are ignored (e.g., O(n/2) is still O(n)).

48:20 Implementing Linear Search in C (Integers)

Creates an array `numbers` with denominations: [20, 500, 10, 5, 100, 1, 50].
Uses a `for` loop to iterate from index 0 to 6.
Compares `numbers[i]` with the user's input; prints 'found' or 'not found'.

59:20 Implementing Linear Search in C (Strings)

Creates a string array `strings` with Monopoly pieces: ["battleship", "boot", "cannon", "iron", "thimble", "top hat"].
Uses `strcmp` from `<string.h>` to compare input string with array elements.
Returns 0 from `strcmp` indicates equality; prints 'found' or 'not found'.

1:09:10 Implementing a Phone Book with Structs in C

Defines a `person` struct with `name` (string) and `number` (string) fields.
Creates an array of `person` structs: `people[3]`.
Initializes `people[0]`, `people[1]`, `people[2]` with names and numbers.
Searches for a name using `strcmp` and prints the corresponding number.

1:21:00 Analyzing Selection Sort

Finds the smallest element and swaps it into the correct position.
Repeats this process for each position in the array.
Has a time complexity of O(n^2) in both worst and best cases.

1:40:10 Analyzing Bubble Sort

Compares adjacent elements and swaps them if they are out of order.
Repeats passes through the list until no swaps are needed.
Worst-case and average-case complexity is O(n^2).
Best-case complexity (already sorted list) is O(n) with an optimization to stop early.

1:49:00 Visualizing Sorting Algorithms

Selection sort: finds smallest element and places it, O(n^2).
Bubble sort: repeatedly swaps adjacent elements, O(n^2) average/worst, O(n) best.
Merge sort: divides, sorts halves, and merges, O(n log n).

1:59:00 Introduction to Recursion

A function that calls itself.
Requires a base case to prevent infinite loops.
Recursive case solves a smaller version of the problem.
Binary search and drawing Mario pyramids are examples.

2:14:00 Merge Sort: Divide and Conquer

Sorts the left half, sorts the right half, then merges the sorted halves.
Base case: If list size is 1, it's already sorted.
The merge step takes O(n) time.
Overall complexity is O(n log n).

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, CS50.