Algorithms

14. Algorithms#

This chapter introduces algorithm foundations using a simple input-process-output model.

Algorithm steps as input, process, and output
Sequence, decision, and repetition as control patterns
Runtime measurement and Big O growth
Search algorithms and tradeoffs
Sorting algorithms and benchmark patterns

Chapter Video

This overview introduces algorithmic thinking, searching, sorting, and Big O reasoning.

Algorithms and Data Structures Tutorial - Full Course for Beginners (5:22:08) by freeCodeCamp.org

Hosted on YouTube; property of its original creator, embedded here for educational reference only.

Learning Objectives

By the end of this chapter, you will be able to:

Describe an algorithm as input, process, and output, and check it against the properties of finiteness, definiteness, and effectiveness
Analyze the time complexity of simple functions and classify their growth with Big O notation, from \(O(1)\) to \(O(n^2)\)
Implement and trace linear search and binary search, and explain why binary search requires sorted input
Choose a search strategy (linear search, binary search, bisect, or hash-based lookup) from data order, lookup count, and memory constraints
Implement insertion sort and merge sort, compare them with quicksort, and sort real data with sorted() and list.sort() using key functions
Measure algorithm performance with time.perf_counter() and timeit, and compare the measured results with Big O predictions

Chapter Flow

Glossary

#	Term	Explanation
1	Algorithm	A step-by-step procedure for solving a problem or completing a task.
2	Input	The data an algorithm receives before it runs.
3	Output	The result an algorithm produces.
4	Correctness	Whether an algorithm produces the right output for valid inputs.
5	Complexity	A description of how an algorithm’s resource use grows with input size.
6	Time complexity	How running time grows as input size grows.
7	Space complexity	How memory use grows as input size grows.
8	Big O notation	A notation for describing an algorithm’s growth rate at a high level.
9	Constant time	A growth pattern where work does not depend on input size.
10	Linear time	A growth pattern where work grows in direct proportion to input size.
11	Logarithmic time	A growth pattern where each step greatly reduces the remaining search space.
12	Benchmarking	Measuring code performance by running timed experiments.
13	Linear search	A search algorithm that checks items one at a time.
14	Binary search	A search algorithm that repeatedly halves a sorted search space.
15	`bisect`	A standard-library module for searching and inserting in sorted sequences.
16	Hash-based lookup	Finding values through a hash table, commonly using a `set` or `dict`.
17	Sorting	Rearranging values into an order.
18	Stability	A sorting property that preserves the relative order of equal-key items.
19	In-place sort	A sort that rearranges the original list instead of returning a full separate copy.
20	Divide and conquer	A design strategy that solves a problem by splitting it into smaller subproblems.
21	Quadratic time	A growth pattern, O(n^2), where work grows with the square of the input size, typical of nested loops.
22	Linearithmic time	A growth pattern, O(n log n), typical of efficient comparison sorts such as merge sort.
23	Insertion sort	A sorting algorithm that builds a sorted section one item at a time by sliding each new item left into place.
24	Bubble sort	A sorting algorithm that repeatedly swaps adjacent out-of-order pairs until a full pass makes no swaps.
25	Merge sort	A divide-and-conquer sort that splits a list in half, sorts each half, and merges the sorted halves.
26	Quicksort	A divide-and-conquer sort that partitions items around a pivot and recursively sorts the smaller and larger groups.
27	Pivot	The element quicksort uses to partition the other items into smaller, equal, and larger groups.
28	Timsort	The stable hybrid of merge sort and insertion sort that Python’s `sorted()` and `list.sort()` use.
29	Key function	A function passed as `key=` to a sort that computes the value used to compare each item.
30	Counting sort	A non-comparison sort that tallies how often each integer value occurs and rebuilds the list from the counts in O(n + k) time.