COMPLEXITY ANALYSIS
Complete Study Notes
Computer Science Fundamentals | Based on gkcs Lecture
1. WHAT IS AN ALGORITHM?
An algorithm is a set of step-by-step instructions that a computer follows to solve a problem and
produce the desired output.
Measuring the Usefulness of an Algorithm
Every algorithm is evaluated on two key parameters:
1 Time
1️⃣ Time Complexity — How long does the algorithm take to run?
2️⃣ Space Space Complexity — How much memory does the algorithm use?
2. TIME COMPLEXITY — DEEP DIVE
Common Misconception
❌ WRONG ✅ CORRECT
t1 (execution time stopwatch measurement) = t1 is merely the execution time — not the time
Time Complexity complexity!
So What IS Time Complexity?
Time complexity is a mathematical function that describes HOW execution time grows as the
input size grows. It is NOT a single measured value — it is a relationship.
Think of it as mapping input size to time:
Input i1 → takes t1 seconds Input i2 → takes t2 seconds
Input i3 → takes t3 seconds ... ...
Plot these points on a 2D graph (x-axis = input size, y-axis = time). Fit a curve through those
points. That curve is a mathematical function f(i) — and THAT gives us time complexity.
3. HOW TO DERIVE TIME COMPLEXITY (Step-by-Step)
Suppose the fitted curve gives us the function:
f(i) = 3i³ + 2i² + 8i + 7
Now follow these four steps to find the Big-O time complexity:
1. Drop all constants → 7 is just a constant; ignore it.
2. Focus on large input → For very large i, smaller-degree terms become insignificant.
3. Keep the highest-degree term only → 3i³ dominates 2i², 8i and 7.
4. Drop constant coefficients → 3i³ becomes simply i³.
Result:
f(i) = 3i³ + 2i² + 8i + 7 → O(n³)
We call this the ORDER of the function — written as O(n³). Here 'n' is the conventional name for
input size.
4. UNDERSTANDING BIG-O NOTATION
Big-O notation expresses the upper bound of an algorithm's growth rate. Common complexities
from fastest to slowest:
Notation Name Meaning
O(1) Constant Time does not change with input size
O(log n) Logarithmic Time grows very slowly — excellent!
O(n) Linear Time grows proportionally with input
O(n log n) Linearithmic Slightly worse than linear — common in sorting
O(n²) Quadratic Time squares as input grows — use carefully
O(n³) Cubic Significantly slower for large inputs
O(2ⁿ) Exponential Grows extremely fast — usually impractical
5. SPACE COMPLEXITY
Space complexity works the same way as time complexity — but instead of measuring
execution time, you measure memory (space) used.
Input i1 → uses s1 memory Input i2 → uses s2 memory Input
i3 → uses s3 memory
Plot the points. Fit a curve. Take the dominant term. Drop constants. Express in Big-O notation.
Same exact steps!
In practice, a mathematician or CS researcher proves the complexity of an
Note algorithm analytically (pen-and-paper) — you do not have to empirically
measure it every time.
6. KEY RULES TO REMEMBER
• Constants are always dropped: O(3n) → O(n)
• Lower-order terms are always dropped: O(n² + n) → O(n²)
• We always think about LARGE input — small inputs don't define the algorithm's nature.
• Big-O is about growth rate, NOT the actual seconds taken.
• 'n' is just the conventional symbol for input size.
7. WORKED EXAMPLE SUMMARY
Original Function Dominant Term Big-O
3i³ + 2i² + 8i + 7 3i³ O(n³)
5n² + 3n + 100 5n² O(n²)
7n log n + 2n 7n log n O(n log n)
42 42 (constant) O(1)
8. QUICK REVISION CHECKLIST
• I know the difference between execution time and time complexity.
• I can map input-time pairs on a graph and understand curve fitting.
• I can identify the dominant term in a polynomial function.
• I can drop constants and lower-order terms to get Big-O.
• I understand that space complexity follows the same method.
• I know common Big-O complexities: O(1), O(log n), O(n), O(n log n), O(n²), O(n³), O(2ⁿ).
"For really large numbers — will my algorithm still make it through? That is the question."
— gkcs