Skip to content

Week 10 - November 18

Class Description

This week we explore algorithmic efficiency, searching, and sorting. Understanding how algorithms scale is fundamental to computer science—it's the difference between a program that processes millions of records instantly versus one that takes hours. You'll learn to analyze complexity, implement classic algorithms, and make informed decisions about which approach to use.

Key Connection: Mathematical Big O analysis → Practical algorithm performance → Implementation choices → Real-world impact at scale.

Key Learning Objectives:

  • Understand why algorithmic efficiency matters for real-world applications
  • Analyze algorithm complexity using Big O notation
  • Distinguish between best case, worst case, and average case performance
  • Implement linear search and understand its O(n) complexity
  • Implement binary search and understand its O(log n) complexity
  • Recognize the requirement that binary search needs sorted data
  • Understand sorting algorithms: insertion sort, bubble sort, and merge sort
  • Compare quadratic O(n²) vs linearithmic O(n log n) sorting algorithms
  • Apply recursive thinking to sorting algorithms
  • Make informed decisions about algorithm selection based on data characteristics

Before Class

Videos to Watch Before Class

CS 5001 - Week 10: Efficiency: Searching & Sorting

CS 5002 - Module 8: Sorting and Big O Notation

CS 5002 - Module 8: Previous Course Videos

LLM Learning Prompts

Use these prompts with ChatGPT, Claude, or other AI assistants to deepen your understanding:

Big O Notation:

Explain Big O notation in simple terms. What does O(n), O(log n), and O(n²) mean? 
Give me concrete examples with code snippets in Python. Why do we drop constants 
and lower-order terms? Show me how to analyze the complexity of loops and nested loops.

Linear Search:

Explain linear search (sequential search) with a Python implementation. What is its 
time complexity and why? When would I use linear search? Walk me through searching 
for an element step-by-step with a concrete example.

Binary Search:

Teach me binary search. Why is it faster than linear search? Why does it require 
sorted data? Show me both iterative and recursive implementations in Python. 
Explain how binary search achieves O(log n) complexity using a concrete example 
with an 8-element array.

Best, Worst, Average Case:

Explain the difference between best case, worst case, and average case complexity. 
For linear search, what are each of these and why? Give me examples of algorithms 
where the best case is significantly better than the worst case.

Insertion Sort:

Explain insertion sort with a visual example. Show me a Python implementation. 
Why is the best case O(n) and worst case O(n²)? When would insertion sort be 
a good choice? Walk me through sorting [5, 2, 8, 1, 9] step by step.

Bubble Sort:

Teach me bubble sort. Show me how it works with a concrete example and Python code. 
Why is it O(n²)? Compare it to insertion sort - which is better and why? Is bubble 
sort ever used in practice?

Merge Sort:

Explain merge sort and the divide-and-conquer paradigm. Show me a Python implementation. 
Why is merge sort O(n log n)? What's the trade-off between merge sort's better time 
complexity and its space usage? Walk me through merge sort on [8, 3, 5, 4, 7, 6, 1, 2].

Complexity Comparison:

I have 1 million items to sort. Compare the performance of O(n²) vs O(n log n) 
algorithms. How many operations would each take? Why does this matter in practice? 
Give me real-world examples where algorithm efficiency makes the difference between 
practical and impractical solutions.

Algorithm Selection:

How do I decide which sorting algorithm to use? What factors should I consider? 
Compare insertion sort, bubble sort, merge sort, and Python's built-in sort. 
When would I implement my own vs use the built-in sort()?

General Understanding:

I'm learning about [topic]. Can you create a small practice problem for me? After 
I attempt it, review my solution and suggest improvements. Also explain the time 
complexity of my approach.

Additional Resources

Interactive Visualizations: