<aside> ⏱️

L1 — Know How Long A Program Takes covers why algorithm efficiency matters (via TSP), how to calculate running time by counting primitive operations, and the three asymptotic notations: Big-Theta, Big-O, and Big-Omega. Read: Section 2.2 and Chapter 3 from Intro. to Algorithms (Cormen et al).

</aside>

📋 At a Glance

• [ ] Understand why brute-force TSP is infeasible for large inputs
• [ ] Know how to measure input size for different problem types
• [ ] Calculate running time by assigning costs to each line of pseudocode
• [ ] Distinguish worst-case, average-case, and best-case running time
• [ ] State the formal definitions of Big-Θ, Big-O, and Big-Ω
• [ ] Prove asymptotic relationships between common functions
• [ ] Analyse insertion sort: best case Θ(n), worst case Θ(n²)
• [ ] Know the standard growth rate hierarchy: 1 < log(n) < √n < n < n log(n) < n² < n³ < ... < 2ⁿ < 3ⁿ < n! < nⁿ
• [ ] Complete Tutorial 1 questions (Q1–Q7)

1. The Travelling Salesman Problem (TSP)

Problem: Given a set of cities and distances between them, find the shortest tour visiting each city exactly once and returning to the start.

Brute-force approach:

• Enumerate all possible tours, check each one, return the shortest
• For N cities, the number of distinct tours is (N−1)!/2 (starting city is fixed, direction is irrelevant)

Why brute force fails:

• 10 cities: solves in ~0.5 seconds (about 200,000 tours)