College · CS 201
Data Structures & Big-O (CS 201) — study guide & practice questions
Complexity analysis, core structures, classic algorithms and algorithm design (greedy, DP, P vs NP).
Study guide
Asymptotic Analysis Foundations
- O gives an upper bound, Ω a lower bound, Θ a tight bound; common orders fastest to slowest: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ).
- Worst-case is the default guarantee unless a question specifically asks for average or best case.
Recurrence Relations & the Master Theorem
- A recursive algorithm's runtime is written as T(n) = aT(n/b) + O(n^d); the Master Theorem compares d to log_b(a) to solve it.
- Divide-and-conquer algorithms like merge sort and binary search split a problem, solve recursively, and combine.
Arrays, Linked Lists & Amortized Analysis
- Arrays: O(1) indexed access, O(n) insert/delete at the front (elements must shift); dynamic arrays double in size for O(1) amortized insertion.
- Linked lists: O(n) access (must walk the list), O(1) insert/delete once you have a pointer to the spot; doubly linked lists add O(1) deletion of a given node.
Stacks, Queues & Trees
- Stack = LIFO (push/pop); queue = FIFO (enqueue/dequeue), both O(1) when implemented properly.
- A balanced binary search tree keeps search, insert and delete at O(log n) by keeping height ~log n; an unbalanced one can degrade to O(n), which self-balancing trees like AVL/red-black prevent.
Heaps & Priority Queues
- A binary heap keeps the min (or max) at the root; insertion and extraction are O(log n), and building a heap from scratch is O(n).
- Heaps back priority queues, used in heap sort (O(n log n), in-place) and algorithms like Dijkstra's.
Hashing in Depth
- Hash tables give O(1) average lookup by mapping keys to array slots via a hash function.
- Collisions (two keys, same slot) are handled by chaining or open addressing; load factor and resizing keep average performance close to O(1).
Sorting Algorithms Compared
- Merge sort: O(n log n) guaranteed, stable, not in-place. Quicksort: O(n log n) average, O(n²) worst case, in-place, usually fastest in practice.
- Heap sort: O(n log n) guaranteed and in-place, but not stable and usually slower in practice than quicksort.
Graph Algorithms
- BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses a stack/recursion and explores depth-first. Both are O(V + E).
- Dijkstra's finds weighted shortest paths (non-negative edges only); Kruskal's/Prim's find minimum spanning trees; dynamic programming reuses overlapping subproblem solutions.
Course modules
8 foundation modules free to read here; 1 advanced module with Pro. Every module ends with a quiz in the app.
1. Asymptotic Analysis Foundations Free
The formal notation for describing how an algorithm scales, and how to read it off real code.
Read the 4 lessons →2. Recurrence Relations & the Master Theorem Free
How to write and solve the equations that describe a recursive algorithm's running time.
Read the 4 lessons →3. Arrays, Linked Lists & Amortized Analysis Free
The two foundational linear structures, and the accounting trick that explains why dynamic arrays feel like O(1).
Read the 4 lessons →4. Stacks, Queues & Trees Free
LIFO and FIFO structures, and the hierarchical structure that makes ordered search efficient — when balanced.
Read the 4 lessons →5. Heaps & Priority Queues Free
The array-backed tree structure that keeps the most important element always one step away.
Read the 4 lessons →6. Hashing in Depth Free
How hash tables achieve average O(1) lookup, and what happens when two keys land in the same place.
Read the 4 lessons →7. Sorting Algorithms Compared Free
Merge sort, quicksort, and heap sort: their guarantees, their trade-offs, and when to reach for each.
Read the 4 lessons →8. Graph Algorithms Free
How to represent graphs efficiently, find shortest paths and minimum spanning trees, and a first look at dynamic programming.
Read the 4 lessons →9. Algorithm Design: Greedy, Dynamic Programming & Intractability Pro · CS 201 · Algorithm Design
When greedy choices work (and when they fail), how to build a dynamic-programming solution step by step, backtracking, and what P vs. NP means in practice.
Sample practice questions
From module 1, Asymptotic Analysis Foundations. Pick your answers, then check them in the app, with an explanation for every question.
1. Rank these from slowest to fastest growing: O(n²), O(log n), O(n), O(1).
2. What is the time complexity of two nested loops, each running independently from 0 to n?
Sample flashcards
4 of the cards in this course's deck. Tap a card to flip it.
SearchingWhat is the time complexity of binary search on a sorted array, and why?
O(log n): each comparison halves the remaining search range.
ListsCompare array and linked list: access by index, and insert at the head.
Array: O(1) access, O(n) head insert (elements shift). Linked list: O(n) access, O(1) head insert.
HashingWhat is the average and worst-case lookup time of a hash table?
O(1) on average with a good hash function and load factor; O(n) worst case when many keys collide into one bucket.
SortingWhat are quicksort's average and worst-case time complexities?
Average O(n log n); worst case O(n²) with consistently bad pivots (for example an already-sorted input with a first-element pivot). It sorts in place using O(log n) stack space on average.
The full course is in LectureMate's Course Library: every module quiz with explanations, the complete flashcard deck with spaced repetition, and a 6-step strategy for Data Structures & Big-O questions. Foundation modules are free; advanced modules need Pro.