Curriculum

Topic 08 · Computer Science

Data Structures & Algorithms

DSA is the vocabulary of efficient computation. Arrays, trees, graphs, hash tables, and the sorting algorithms that operate on them determine whether your AI system runs in milliseconds or minutes.

The idea

Every data structure is a tradeoff between operation costs. Arrays: O(1) random access, O(n) insertion. Linked lists: O(1) insertion, O(n) access. Binary search trees: O(log n) for all three when balanced. Hash tables: O(1) average for all three.

Big-O notation describes asymptotic complexity—how runtime or memory scales with input size n. O(1) is constant, O(log n) is logarithmic (binary search), O(n) is linear, O(n log n) is the lower bound for comparison-based sorting, O(n²) is quadratic (nested loops).

Graphs represent relationships. BFS (breadth-first search) finds shortest paths in unweighted graphs. DFS (depth-first search) explores deep paths and detects cycles. Dijkstra's algorithm finds shortest paths in weighted graphs. A* adds a heuristic to Dijkstra for faster directed search.

T(n) = O(n log n) (merge sort, heap sort, quick sort average)

Lower bound for comparison-based sorting. No algorithm can do better in the worst case.

What to hold onto

  • Dynamic ProgrammingBreak the problem into overlapping subproblems, solve each once, store results (memoisation or tabulation). Fibonacci, LCS, shortest path—all DP.
  • HeapA binary heap supports O(1) peek-min/max and O(log n) insert and extract. Foundation of priority queues, Dijkstra, and heap sort.
  • Hash CollisionsChaining (linked list per bucket) or open addressing (linear/quadratic probing, double hashing). Load factor α < 0.7 keeps average O(1) performance.

Live: Sorting Algorithm Arena

Watch Bubble Sort vs Quick Sort rearrange elements with step-by-step swaps and comparisons.

Swaps: 0 | Compares: 0

Quick answers

What are Data Structures?

Data structures are ways of organising data to enable efficient access and modification. Common structures include arrays (O(1) access), linked lists (O(1) insertion), hash tables (O(1) average lookup), binary search trees (O(log n) for balanced trees), and graphs (relationships between entities). The right structure determines algorithmic efficiency.

What is Big-O notation?

Big-O notation describes the asymptotic upper bound on an algorithm's time or space complexity as input size n grows. O(1) is constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic (optimal comparison sort), and O(n²) quadratic. It abstracts away constants to reveal how algorithms scale.