CS50x 2026 – Lecture 3 – Algorithms

Understanding Algorithms in Computer Science

CS50 Lecture 3 provides a comprehensive introduction to algorithms, one of the core pillars of computer science education at Harvard University. This lecture, delivered by David J. Malan, spans two hours and covers essential algorithmic concepts that form the foundation for efficient problem-solving and software development. Algorithms are step-by-step procedures for solving problems, and understanding how to design, analyze, and optimize them is critical for any aspiring computer scientist or programmer.

Linear and Binary Search Methods

The lecture begins with searching algorithms, demonstrating how different approaches to finding data can dramatically impact performance. Linear search is introduced as the simplest method: iterating through data sequentially until the target element is found. While intuitive and easy to implement, linear search examines every element in the worst case. Binary search is then presented as a more efficient alternative, operating on sorted data by repeatedly dividing the search space in half. This divide-and-conquer strategy reduces the number of comparisons from potentially n operations to approximately log(n), showcasing how algorithmic thinking can yield exponential improvements in performance.

Running Time and Computational Complexity

A pivotal section of the lecture explores running time analysis, introducing the concept of computational complexity and Big O notation. Rather than measuring time in seconds (which depends on hardware), algorithms are analyzed by counting operations and understanding how they scale as input size grows. The lecture demonstrates why this matters: an algorithm that takes microseconds on small inputs might become impractical on large datasets without proper complexity analysis. Students learn to classify algorithms by their efficiency characteristics, comparing constant time O(1), logarithmic O(log n), linear O(n), and quadratic O(n²) operations.

Practical Implementation in C

Theory transitions to practice through live coding demonstrations. The search.c example shows how linear and binary search are implemented in the C programming language, making abstract concepts concrete. Similarly, phonebook.c demonstrates practical applications where search algorithms solve real-world problems like looking up contact information. These implementations help students bridge the gap between understanding an algorithm conceptually and translating that understanding into executable code. The lecture emphasizes that implementation details matter, and data structure choices (like using arrays or structs) influence both code clarity and algorithm performance.

Structs and Data Organization

Before diving into sorting, the lecture introduces structs—a fundamental C construct for organizing related data into cohesive units. This concept is essential because sorting algorithms often operate on structured records rather than simple integers. By grouping related fields (such as a person's name and phone number in a phonebook application), structs enable more realistic problem-solving scenarios and demonstrate why proper data modeling is prerequisite to efficient algorithm design.

Sorting Algorithms and Efficiency

The sorting section covers multiple approaches, each with distinct characteristics. Selection sort is explained as a method that repeatedly finds the minimum element and moves it to its correct position, resulting in O(n²) complexity. Bubble sort is then presented, using a comparison-and-swap strategy to gradually move elements toward their sorted positions, also achieving O(n²) performance. While these simpler algorithms are useful for learning sorting principles, the lecture emphasizes their limitations on large datasets. Merge sort is introduced as a far more sophisticated approach, employing a divide-and-conquer strategy that achieves O(n log n) complexity—a dramatic improvement that becomes significant as data sizes grow from thousands to millions of elements.

Recursion and Algorithm Structure

Recursion is explored as both a conceptual framework and a practical tool for algorithm design. The lecture demonstrates how functions can call themselves to solve smaller instances of the same problem, ultimately reducing to a base case. This is illustrated through simple examples using iteration.c and recursion.c, showing equivalent solutions implemented iteratively and recursively. Understanding recursion is essential for grasping merge sort, which inherently relies on breaking problems into smaller subproblems and combining their solutions—a pattern fundamental to many advanced algorithms.

Comparative Performance Analysis

The lecture concludes with a sort race, visually comparing how different sorting algorithms perform on the same dataset. This dramatic demonstration illustrates why algorithmic analysis matters in practice. Watching selection sort and bubble sort lag significantly behind merge sort on substantial inputs drives home the point that theoretical complexity analysis translates directly to real-world performance differences. Students witness firsthand why choosing the right algorithm isn't merely an academic exercise but a practical necessity for writing responsive, scalable software.