CS50x: Introduction to Computer Science Algorithms Syllabus

What is the worst-case running time of selection sort?

$O(n^{2})$ — it performs $(n-1) + (n-2) + \cdots + 1 = \frac{n(n-1)}{2}$ comparisons.

What is the best-case running time of selection sort, and why?

$\Omega(n^{2})$ — even on an already sorted array, selection sort must still scan the entire unsorted portion every round to confirm the minimum, so it cannot exit early.

Give the formula for the total number of comparisons selection sort makes on $n$ elements.

$$\sum_{k=1}^{n-1} k = \frac{n(n-1)}{2} = \frac{n^{2}}{2} - \frac{n}{2},$$ which is $O(n^{2})$ after dropping constants and lower-order terms.

Describe the steps of selection sort.

For $i$ from $0$ to $n-2$: search positions $i$ through $n-1$ for the smallest element, then swap it with the element at position $i$. After each round, the sorted region at the front grows by one element.

Compare bubble sort and selection sort on a fully sorted input.

Both are $O(n^{2})$ in the worst case, but optimized bubble sort detects the sorted input and finishes in $\Omega(n)$, while selection sort still takes $\Omega(n^{2})$ because it always scans for the minimum.

What is merge sort?

A recursive divide-and-conquer sorting algorithm: split the array into two halves, recursively sort each half, then merge the two sorted halves into one sorted array.

State merge sort in three lines of pseudocode.

If the array has only $1$ element, it is already sorted (return). Otherwise: sort the left half, sort the right half, then merge the two sorted halves.

What is the worst-case running time of merge sort?

$O(n \log n)$ — asymptotically faster than the $O(n^{2})$ of bubble sort and selection sort.

What is the best-case running time of merge sort?

$\Omega(n \log n)$ — merge sort always splits and merges fully, so even a sorted input takes $n \log n$ time; hence merge sort is $\Theta(n \log n)$.

Why does merge sort run in $O(n \log n)$ time?

Halving the array repeatedly creates about $\log_{2} n$ levels of division, and merging at each level touches all $n$ elements, giving total work $n \times \log_{2} n$.

What is the base case of merge sort?

An array (or subarray) of size $1$: a single element is already sorted, so the recursion stops and returns immediately.

How does the merge step combine two sorted halves?

Repeatedly compare the front (smallest remaining) elements of the two halves, copy the smaller one into the output, and advance in that half; when one half is exhausted, copy over the rest of the other half.

What is the main trade-off merge sort makes for its speed?

Extra memory: it needs additional space (on the order of $O(n)$) to hold elements while merging, whereas bubble sort and selection sort sort in place.

What does Big $O$ notation describe?

An upper bound on running time — how the algorithm's time grows with input size $n$ in the worst case (e.g. linear search is $O(n)$).

What does Big $\Omega$ (Omega) notation describe?

A lower bound on running time — the best case for the algorithm (e.g. linear search is $\Omega(1)$, since the target might be found immediately).

What does Big $\Theta$ (Theta) notation describe, and when does it apply?

A tight bound: when an algorithm's upper and lower bounds coincide, i.e. $O$ and $\Omega$ are the same, we write $\Theta$ (e.g. selection sort is $\Theta(n^{2})$, merge sort is $\Theta(n \log n)$).

Order these common running times from fastest to slowest: $O(n^{2})$, $O(1)$, $O(n \log n)$, $O(n)$, $O(\log n)$.

$$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^{2})$$

Why is an algorithm taking $\frac{n^{2}}{2} - \frac{n}{2}$ steps still classified as $O(n^{2})$?

Asymptotic notation ignores constant factors and lower-order terms because, as $n \to \infty$, the $n^{2}$ term dominates growth; only the dominant term matters.

What does a running time of $O(1)$ mean? Give an example.

Constant time: the number of steps does not grow with input size $n$. Example: accessing an array element by index, or checking the first element of a list.

Give the worst-case ($O$) and best-case ($\Omega$) running times of linear search and binary search.

Linear search: $O(n)$ and $\Omega(1)$. Binary search: $O(\log n)$ and $\Omega(1)$. Binary search is faster in the worst case but requires sorted data.

Give the worst-case ($O$) and best-case ($\Omega$) running times of bubble sort, selection sort, and merge sort.

Bubble sort: $O(n^{2})$, $\Omega(n)$. Selection sort: $O(n^{2})$, $\Omega(n^{2})$. Merge sort: $O(n \log n)$, $\Omega(n \log n)$.

If you double the input size $n$ of an $O(n^{2})$ algorithm, roughly how much longer does it take?

About $4$ times longer, since $(2n)^{2} = 4n^{2}$.

When is it worth sorting an array first ($O(n \log n)$ with merge sort) rather than using linear search directly?

When you will search the data many times: sorting once costs $O(n \log n)$, but then every search is only $O(\log n)$ with binary search instead of $O(n)$ each time.

What is a recursive function?

A function that calls itself, solving a problem by reducing it to one or more smaller instances of the same problem until a trivially solvable case is reached.

What two essential parts must every correct recursive function have?

1) A base case: a condition where the function stops calling itself and returns directly. 2) A recursive case: a call to itself on a smaller version of the problem that moves toward the base case.

What is a base case in recursion, and what is its purpose?

The simplest input for which the answer is returned directly without further recursive calls. It terminates the recursion, guaranteeing the chain of self-calls eventually stops.

What happens if a recursive function has no (reachable) base case?

It calls itself forever: each call adds a new frame to the call stack until memory is exhausted, causing a stack overflow and crashing the program (e.g. a segmentation fault in C).

Define the factorial function recursively, including its base case.

$$n! = n \cdot (n-1)! \quad \text{for } n \geq 1, \qquad 0! = 1.$$ The base case $0! = 1$ (equivalently $1! = 1$) stops the recursion.

Describe binary search as a recursive function, naming its base cases.

Recursive case: compare the target to the middle element and recurse on the left or right half. Base cases: the middle element equals the target (found), or the search range is empty (not found).

Which of the algorithms covered in CS50 is naturally recursive, and what makes it so?

Merge sort: it solves the problem by calling itself on the left half and the right half of the array (recursive cases), stopping when a subarray has one element (base case), then merging results.