Week 3: Algorithms
Searching and sorting as things you can watch: a phone book torn in half, and three sorting strategies racing on the same shuffled deck.
9 topics · 37 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
What Makes an Algorithm Efficient
- How it worksHow does counting the worst-case number of steps let you judge an algorithm without ever running it?
- Going furtherWhat happens to an algorithm's efficiency ranking when the input is already almost sorted?
- Common mistakeWhy isn't the algorithm that feels intuitively obvious always the one with the best worst-case running time?
- Ties togetherHow does the phone book's halving strategy connect to how binary search will work on a sorted array?
Your turn1 of 2
An algorithm checks every one of a list's elements in the worst case. For a list of 70 elements, how many checks does the worst case require?Linear Search
- How it worksHow does linear search check one element after another until it finds a match or runs out of elements?
- Worked exampleWalk me through linear search looking for the number 7 in the unsorted list 4, 9, 7, 2, 5.
- Common mistakeWhy isn't linear search just a bad algorithm — when is it actually the right choice to make?
Your turn1 of 2
Linear search looks for a target that happens to sit at position 35 of an array (counting the first position as 1). How many comparisons does linear search make before finding it?Binary Search
- How it worksHow does binary search throw away half of the remaining sorted list with every single comparison?
- How it worksHow does comparing your target to the middle element tell binary search which half to keep?
- Worked exampleWalk me through binary search finding the number 23 in the sorted list 2, 5, 8, 15, 23, 41, 67.
- Common mistakeWhy doesn't binary search work at all on a list that hasn't been sorted first?
- Going furtherWhat happens to the number of steps binary search needs as the list grows from 1000 to 1,000,000?
Your turn1 of 2
Binary search runs on a sorted list of 27 elements, halving the remaining range with every comparison. How many comparisons does it need in the worst case to narrow down to one element?Big O and Asymptotic Notation
- How it worksHow does Big O notation describe an algorithm's worst-case running time while ignoring constant factors?
- How it worksHow does O(log n) end up so much flatter than O(n) as n grows into the millions?
- Worked exampleFind the Big O running time of a single loop that checks every one of n elements exactly once.
- Common mistakeWhy isn't an O(n2) algorithm always slower in practice than an O(n log n) one?
Your turn1 of 2
An O(n) algorithm and an O(n2) algorithm are both run on an input of size 21. Using n and n2 as their step counts, how many more steps does the O(n2) algorithm take than the O(n) one?Bubble Sort
- How it worksHow does bubble sort repeatedly swap neighboring elements that are out of order until nothing moves?
- Common mistakeWhy isn't bubble sort finished after just one pass through the list?
- Worked exampleWalk me through bubble sort's first full pass over the list 5, 1, 4, 2, 3.
- Going furtherWhat happens to bubble sort's running time when it is handed a list that is already sorted?
Your turn1 of 2
Bubble sort makes one comparison per adjacent pair in each full pass over the list. How many comparisons does a single full pass make over a list of 35 elements?Selection Sort
- Worked exampleWalk me through selection sort's first two passes over the list 5, 1, 4, 2, 3.
- Common mistakeWhy isn't selection sort just bubble sort wearing a different name?
- Going furtherWhat happens to selection sort's running time on an already-sorted list, compared to bubble sort's?
Your turn1 of 2
Find how many comparisons selection sort needs in the worst case to sort a list of 29 elements.Merge Sort
- How it worksHow does merge sort recursively split a list in half until each piece has just one element?
- Worked exampleWalk me through merge sort splitting the list 5, 1, 4, 2, 3 down to single elements.
- Worked exampleWalk me through merge sort merging the sorted halves 1, 5 and 2, 3, 4 back into one sorted list.
- Common mistakeWhy isn't merge sort's extra memory for temporary arrays a sign that it's a worse algorithm than bubble sort?
- Going furtherWhat happens to merge sort's running time as the list size grows, compared to bubble sort's?
Your turn1 of 2
Merge sort keeps splitting an array of 27 elements in half until every piece holds a single element. How many splitting levels does this take?Recursion
- How it worksHow does a base case stop a recursive function from calling itself one time too many?
- Common mistakeWhy isn't a recursive function just an infinite loop wearing a disguise?
- Going furtherWhat happens on the call stack as a recursive factorial function counts down from 5 to its base case?
- Ties togetherHow does merge sort's habit of splitting a list in half connect to how binary search halves its list too?
Your turn1 of 2
A recursive factorial function counts down from 21 to its base case at 0, making one recursive call per step. How many total function calls are on the stack, including the initial call, right before it starts returning?Comparing Sorting Algorithms Side by Side
- How it worksHow do bubble sort, selection sort, and merge sort each spend a different number of comparisons on the same list?
- Worked exampleFind how many comparisons selection sort needs in the worst case to sort a list of 5 elements.
- Common mistakeWhy isn't the sorting algorithm with the fewest lines of code automatically the fastest one?
- Going furtherWhat happens to the gap between merge sort and bubble sort as the list grows from 10 elements to 10,000?
- Ties togetherHow does merge sort's O(n log n) running time connect back to binary search's O(log n)?
Your turn1 of 2
Find how many comparisons selection sort needs in the worst case to sort a list of 29 elements.