✅ DSA Roadmap: Part 1 – Time & Space Complexity ⏱️📊

Understanding time and space complexity is crucial for writing efficient code. It helps you estimate how your algorithm will perform as input size grows.

1️⃣ What is Time Complexity? 
Time complexity tells us how fast an algorithm runs based on input size (n). It doesn't measure time in seconds — it measures growth rate.

Example (Python):

for i in range(n):
    print(i)

Runs n times → O(n) time

Example (Java):

for (int i = 0; i < n; i++) {
    System.out.println(i);
}

Example (C++):

for (int i = 0; i < n; i++) {
    cout << i << endl;
}

2️⃣ Common Time Complexities (Best to Worst): 
O(1) – Constant (e.g., array access) 
O(log n) – Logarithmic (e.g., binary search) 
O(n) – Linear (e.g., single loop) 
O(n log n) – Efficient sorting (e.g., merge sort) 
O(n²) – Quadratic (e.g., nested loops) 
O(2ⁿ), O(n!) – Very slow (e.g., recursive brute force)

3️⃣ What is Space Complexity? 
It tells us how much extra memory your code uses depending on input size.

Example:

arr = [0] * n  # O(n) space

If no extra structures are used → O(1) space

4️⃣ Why It Matters 
• Handles large inputs without crashing 
• Crucial in coding interviews 
• Essential for scalable systems

5️⃣ Practice Task – Guess the Complexity

a) Nested loop

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println(i + ", " + j);
    }
}

// O(n²)

b) Binary search

while (low <= high) {
    int mid = (low + high) / 2;
    if (arr[mid] == target) break;
}

// O(log n)

c) Recursive Fibonacci

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

// O(2^n)

Takeaway: 
Always analyze two things before solving any problem: 
– How many steps will this take? (Time) 
– How much memory does it use? (Space)

💬 Tap ❤️ for more