A-Level CS Flashcards: Algorithms

Computer Science — Algorithms Flashcards

20 interactive flashcards for A-Level Computer Science. Press Space to flip, rate 1-4.

What These Flashcards Cover

These flashcards test your knowledge of fundamental algorithms and their analysis. You should be able to describe how each algorithm works, state its time complexity, and explain when it is appropriate to use.

Key areas:

• Linear Search: Check each element in sequence. Time complexity: $O(n)$. Works on unsorted data. Simple but inefficient for large datasets.
• Binary Search: Repeatedly divide a sorted list in half. Time complexity: $O(\log n)$. Requires sorted data. Much faster than linear search for large datasets but needs pre-sorted input.
• Bubble Sort: Repeatedly swap adjacent elements if they are in the wrong order. Time complexity: $O(n^{2})$. Simple to implement but very slow for large lists.
• Quick Sort: Choose a pivot, partition the list into elements less than and greater than the pivot, then recursively sort each partition. Average time: $O(n \log n)$. Worst case: $O(n^{2})$. Generally the fastest general-purpose sort.
• Merge Sort: Divide the list in half recursively until single elements remain, then merge sorted halves. Time complexity: $O(n \log n)$ in all cases. Stable sort but requires extra memory.
• Graph Algorithms: Dijkstra’s algorithm finds the shortest path from a source to all other vertices in a weighted graph with non-negative edges. Time complexity: $O(n^{2})$ with adjacency matrix. A* uses a heuristic to find the shortest path more efficiently.
• Tree Traversals: In-order (left, root, right), pre-order (root, left, right), post-order (left, right, root). In a binary search tree, in-order traversal gives sorted output.
• Big-O Notation: Describes how the time or space requirements grow with input size. $O(1)$ constant, $O(\log n)$ logarithmic, $O(n)$ linear, $O(n \log n)$ linearithmic, $O(n^{2})$ quadratic, $O(2^{n})$ exponential.

Intuition

Think of searching like finding a word in a dictionary. Linear search is reading every page from the start. Binary search is opening the middle, deciding which half to look in, and repeating — you eliminate half the remaining options each time, which is why it is so fast.

Sorting is like organising a bookshelf. Bubble sort is comparing adjacent books and swapping them one at a time. Merge sort is splitting the shelf in half, sorting each half separately, then merging them back together. Quick sort is picking one book as a reference and putting all smaller books to its left and larger ones to its right.

Common Pitfalls

1. Confusing best, average, and worst case. Binary search is $O(\log n)$ in the worst case. Quick sort is $O(n \log n)$ on average but $O(n^{2})$ in the worst case. Always specify which case you are describing.
2. Forgetting that binary search requires sorted data. If the data is not sorted, you must sort it first (costing $O(n \log n)$), which negates the benefit for a single search.
3. Misunderstanding Big-O. Big-O describes the growth rate, not the exact time. $O(n)$ and $O(2n)$ are both $O(n)$ because constants are dropped.
4. Confusing stable and unstable sorts. A stable sort preserves the relative order of equal elements. Bubble sort and merge sort are stable; quick sort and heap sort are not.

Cross-References

• Number Systems: Binary systems are foundational
• Boolean Algebra: Logic underpins computing
• Graph Algorithms: Algorithms solve computational problems