Comparing algorithms and ADTs in algorithms
Comparing algorithms
- How do we say one algorithm is "better" than another?
- Big-O describes how the running time grows with the input size.
- We also weigh memory, stability and simplicity.
Time complexity (Big-O)
- Time complexity is how the running time grows with input size $n$, written in Big-O (the dominant term):
- $O(1)$ constant · $O(\log n)$ binary search · $O(n)$ linear search · $O(n \log n)$ good sorts · $O(n^2)$ bubble/insertion sort.
- A smaller order is better at scale, even if another algorithm is faster for tiny $n$.
Practice
Which Big-O describes binary search?
Halving the range each step is logarithmic — O(log n).
Practice
Which Big-O describes bubble sort in the worst case?
Two nested loops over n elements give O(n²).
Practice
Match each algorithm to its time complexity.
Linear search is O(n), binary search O(log n), bubble sort O(n²).
Space complexity and other criteria
- Space complexity is the extra memory needed: bubble/insertion sort use $O(1)$ extra (in place); merge sort uses $O(n)$; recursion uses stack memory proportional to its depth.
- There's often a time–memory trade-off.
- Also consider simplicity, stability, and adaptiveness (faster on nearly-sorted data).
Practice
An "in place" sort:
In-place algorithms (like bubble and insertion sort) sort within the original array, using constant extra space.
ADTs inside algorithms
- The ADTs from data structures appear inside many algorithms:
- a stack drives depth-first traversal and undo; a queue drives breadth-first traversal.
- ADTs can be built from other ADTs (a queue from two stacks; a stack from a linked list; a binary tree from nodes with two child pointers) — layering separates concerns.
Practice
Which ADT naturally drives a depth-first traversal?
A stack (LIFO) gives depth-first; a queue (FIFO) gives breadth-first.
You've got it
Key idea
- Big-O ranks growth: $O(1) < O(\log n) < O(n) < O(n\log n) < O(n^2)$
- space complexity = extra memory; in place = $O(1)$ extra
- also weigh stability, simplicity, adaptiveness — and the time–memory trade-off
- stack → DFS, queue → BFS; ADTs can be built from other ADTs