1. What is Algorithm Complexity?
- Algorithm = step-by-step procedure to solve a problem.
- Complexity = how much time or memory it needs as input size grows.
- We measure this using Big-O notation.
2. Why Big-O Notation?
- It describes the growth rate, not the exact time.
- Helps compare algorithms (fast vs slow) independent of hardware.
- Example: One algorithm takes 1 second for 1000 inputs, another takes 10 seconds — Big-O tells us how this scales when inputs grow to 1 million.
3. Common Complexities (with examples)
🔹 O(1) → Constant time
- Same time, no matter the input size.
- Example: access
arr[5], simple formula liken(n+1)/2.
🔹 O(log n) → Logarithmic time
- Input size shrinks in half each step.
- Example: Binary Search in a sorted array.
🔹 O(n) → Linear time
- One loop over all
nitems. - Example: Find the max element in an array.
🔹 O(n log n) → Linearithmic time
- Appears in efficient sorting algorithms.
- Example: Merge Sort, Quick Sort.
🔹 O(n²) → Quadratic time
- Double loop → compare all pairs.
- Example: Bubble Sort, checking all pairs in a matrix.
🔹 O(2ⁿ) → Exponential time
- Doubles work for each extra input.
- Example: Recursive Fibonacci, brute force subsets.
🔹 O(n!) → Factorial time
- Explodes very fast → all permutations.
- Example: Traveling Salesman (brute force).
4. Formula vs Algorithm
- Formula: Already solved shortcut, runs in O(1).
- Example: Sum of first
nnumbers =n(n+1)/2.
- Example: Sum of first
- Algorithm: Step-by-step method to compute the answer.
- Example: Loop through numbers and add one by one = O(n).
✅ TL;DR:
- Big-O tells us how fast/slow an algorithm grows with input size.
- Formulas are direct (O(1)), algorithms can vary (O(n), O(n log n), etc).
- Choosing the right algorithm = huge performance difference in real-world apps.
If you found this helpful, consider supporting my work at ☕ Buy Me a Coffee.
Top comments (1)
My understanding is Big O (or Landau's symbol) is also used as an indication of space complexity. Check out this page: freecodecamp.org/news/big-o-notati...