Recitation Week 4 | CSE310: Data Structures and Algorithms
A search algorithm that's O(n²) vs O(log n) makes the difference between milliseconds and hours when searching millions of records.
The process of determining the computational complexity of algorithms in terms of time and space resources required.
Real machines vary dramatically in speed, architecture, and capabilities. We need a standard model for fair comparison.
A theoretical computer model where any memory location can be accessed in constant time O(1).
Algorithm A takes 100n + 50 operations, Algorithm B takes 2n² + 10n + 5 operations. Which is better?
$f(n) = O(g(n))$ if $\exists$ positive constants $c$ and $n_0$ such that $f(n) \leq c \cdot g(n)$ for all $n \geq n_0$
f(n) will never grow faster than g(n) (up to a constant factor) for sufficiently large n.
Big-O gives us a "ceiling" - the algorithm will NOT perform worse than this bound.
■ f(x) = 3x² + 20x
■ g(x) = x²
■ c·g(x) = 4x²
Step 1: Choose $g(n) = n^2$
Step 2: Find constants $c$ and $n_0$ such that $3n^2 + 20n \leq c \cdot n^2$ for $n \geq n_0$
Step 3: Rearrange: $3n^2 + 20n \leq c \cdot n^2$
Step 4: $3 + \frac{20}{n} \leq c$
Step 5: For $n \geq 20$, $\frac{20}{n} \leq 1$, so $c = 4$ works with $n_0 = 20$
Choose $c = 6$, $n_0 = 3$. For $n \geq 3$: $5n + 3 \leq 5n + n = 6n$
For large n, $\log n < n$, so $n \log n < n^2$. Thus $f(n) < 2n^2$ with $c = 2$
Exponential functions grow faster than any polynomial
function linearSearch(array, target):
for i = 0 to length(array) - 1:
if array[i] == target:
return i
return -1Target is first element
Target is last element or not found
Target is in middle on average
No extra space needed
function binarySearch(sortedArray, target):
left = 0
right = length(array) - 1
while left <= right:
mid = (left + right) / 2
if array[mid] == target:
return mid
else if array[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Target is middle element
Search until one element left
On average need log n comparisons
Iterative version uses constant space
function selectionSort(array):
n = length(array)
for i = 0 to n-2:
minIndex = i
for j = i+1 to n-1:
if array[j] < array[minIndex]:
minIndex = j
swap(array[i], array[minIndex])
return arrayAlways does same number of comparisons
Always does same number of comparisons
Always does same number of comparisons
Sorts in place
function mergeSort(array):
if length(array) <= 1:
return array
mid = length(array) / 2
left = mergeSort(array[0...mid-1])
right = mergeSort(array[mid...end])
return merge(left, right)
function merge(left, right):
result = []
// merge two sorted arrays in O(n) timeAlways divides and merges
Always divides and merges
Always divides and merges
Needs extra space for merging
function fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)Exponential regardless of input
Exponential growth
Exponential growth
Recursion stack depth
Big-O gives an upper bound, not the exact time. An O(n²) algorithm might actually run in O(n) time for specific inputs.
While asymptotically irrelevant, constants matter for small inputs in practice.
Big-O can describe best, average, or worst-case complexity. Context matters!
$f(n) = \Omega(g(n))$ if $\exists$ positive constants $c$ and $n_0$ such that $f(n) \geq c \cdot g(n)$ for all $n \geq n_0$
f(n) will never grow slower than g(n) (up to a constant factor) for sufficiently large n.
Big-Omega gives us a "floor" - the algorithm will NOT perform better than this bound.
■ f(x) = 0.01x² + 20000
■ g(x) = x²
■ c·g(x) = 0.005x²
Information-theoretic lower bound: need at least $\log(n!)$ comparisons to distinguish n! permutations.
Choose $c = 3$, $n_0 = 1$. For all $n \geq 1$: $f(n) \geq 3n^2$
Must read all n² input elements, so can't be faster than $\Omega(n^2)$
$f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$
$\exists$ positive constants $c_1$, $c_2$, and $n_0$ such that $c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n)$ for all $n \geq n_0$
Big-Theta gives us the most precise bound - f(n) and g(n) have the same growth rate.
■ f(x) = 2x² + 3x + 1
■ c₁·g(x) = 2x²
■ c₂·g(x) = 6x²
Lower bound: $f(n) \geq 2n^2$ for $n \geq 1$ (so $\Omega(n^2)$)
Upper bound: $f(n) \leq 6n^2$ for $n \geq 1$ (so $O(n^2)$)
Both best and worst case are $n \log n$ - optimal comparison-based sorting
Theta notation tells us the exact growth rate, while O and Omega only give one-sided bounds.
Key Rule: Each function grows strictly faster than all previous ones
Big-O: If $\lim_{n \to \infty} \frac{f(n)}{g(n)} < \infty$, then $f(n) = O(g(n))$
Big-Omega: If $\lim_{n \to \infty} \frac{f(n)}{g(n)} > 0$, then $f(n) = \Omega(g(n))$
Big-Theta: If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = c > 0$, then $f(n) = \Theta(g(n))$
Little-o: If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, then $f(n) = o(g(n))$
If $f(n) \leq g(n)$ for every integer $n$, is $f(n) = O(g(n))$?
Consider the definition of Big-O. What values can c and n₀ take?
If f(n) ≤ g(n) always holds, try c = 1 and n₀ = 1.
The Big-O definition requires f(n) ≤ c·g(n) for n ≥ n₀. With c = 1 and n₀ = 1, we get f(n) ≤ 1·g(n) = g(n) for all n ≥ 1, which matches our given condition.
Answer: Yes! The condition f(n) ≤ g(n) for every n satisfies the Big-O definition with c = 1 and n₀ = 1.
If $f(n) = O(g(n))$, does $f(n) \leq g(n)$ for every integer $n$?
Big-O says f(n) ≤ c·g(n) for n ≥ n₀. What about n < n₀?
Consider f(n) = 100n and g(n) = n². Is f(n) = O(g(n))? What about when n = 1?
For f(n) = 100n and g(n) = n², we have f(n) = O(g(n)) with c = 100 and n₀ = 1. But f(1) = 100 > 1 = g(1), so the inequality doesn't hold for every n.
Answer: No! Big-O only guarantees the inequality for n ≥ n₀, not necessarily for every integer n. Small values can violate the inequality.
If $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 8$, what can we conclude about the relationship between f(n) and g(n)?
When the limit equals a positive constant, what does this tell us about both upper and lower bounds?
A limit of 8 means f(n) ≈ 8·g(n) for large n. This gives us both directions of the inequality.
Since the limit is a positive finite constant (8), f(n) grows at the same rate as g(n), just scaled by a constant factor. This means f(n) = Θ(g(n)).
Answer: f(n) = Θ(g(n)). A finite positive limit indicates both functions have the same growth rate, giving us a tight bound.
Linear Search: O(n) vs Binary Search: O(log n)
Winner: Binary search for sorted data
Bubble Sort: O(n²) vs Merge Sort: O(n log n)
Winner: Merge sort for large datasets
Naive Multiplication: O(n³) vs Strassen's: O(n^2.807)
Winner: Strassen's for very large matrices
Index structures (B-trees) reduce search from O(n) to O(log n), making million-record queries feasible.
PageRank algorithm's efficiency determines how quickly search results are returned to billions of users.
Training complexity affects model feasibility. O(n³) algorithms become impractical for large datasets.
Real-time rendering requires algorithms that can maintain 60+ FPS, making complexity analysis critical.
Practice analyzing algorithms, prove complexity relationships, and apply these concepts to real problems!