Algorithm Complexity Flashcards
What is an algorithm?
A clear list of steps to solve a problem. It must work well, be easy to follow, and end after a few steps.”
✅ Examples: recipe, sorting numbers
❌ Not examples: recognizing a face, judging beauty
Examples: Recipe for soup ✅, Sorting numbers ✅, Recognizing a face ❌, Ordering by beauty ❌.
What is algorithm efficiency?
How well an algorithm uses things like time, memory, or power
What is time complexity?
Shows how the number of steps grows as the input size (n) gets bigger, usually looking at the worst case
What is empirical analysis?
Running the algorithm with different input sizes and timing how long it takes
What is Big-O notation?
Big O tells how fast an algorithm slows down as the input gets bigger:
✅ It drops constants and lower terms
📈 It tells how fast the algorithm grows with big inputs
What is the Big-O classification for T(n)=n?
O(n)
What is the Big-O classification for T(n)=n+2?
O(n)
What is the Big-O classification for T(n)=2n²?
O(n²)
What is the Big-O classification for T(n)=1000?
O(1)
What is the Big-O classification for T(n)=n²+n+1?
O(n²)
What are common Big-O classes?
- O(1) – Constant time
- O(log n) – Logarithmic
- O(n) – Linear
- O(n log n) – Log-linear
- O(n²) – Quadratic
- O(n³) – Cubic
- O(2ⁿ) – Exponential (intractable)
What is the time complexity of a Linear Search?
T(n) = n → O(n)
What is the time complexity of a Binary Search?
T(n) = log₂(n) → O(log n)
What is the time complexity for Matrix-Vector Multiplication?
Requires 2n² operations → O(n²)
How do functions f(n)=n² and g(n)=n²−3n+2 behave for large n?
As inputs get large, the smaller terms don’t matter, so we focus only on the biggest one
How to compute total complexity in sequential phases?
When combining parts, keep the one that grows the fastest. For example, O(n) + O(n²) becomes O(n²)
How to compute total complexity in nested calls/compositions?
When steps happen inside each other (like loops inside loops), multiply their complexities. For example, O(n) × O(log n) = O(n log n)
What are some Big-O tips?
Count loops (and nested loops)
Drop constants (e.g. 5n → n)
Focus on how it grows with big inputs
Use worst-case time
What is the likely Big-O for code with one nested loop?
O(n²)
What is the likely Big-O for code with triple nested loops?
O(n³)
What is the likely Big-O for a single loop doing log-based halving?
O(log n)
What are lessons from complexity regarding efficient algorithms?
Fast algorithms save time for big inputs. Some problems are just slow no matter what (like exponential ones)
What can make a hard problem tractable?
Sometimes we change the problem or accept close-enough answers to make it faster to solve
