💡 Time Complexity Kya Hai?

Socho:

Tum ek school mein ho, aur teacher bole ki "Class ke sab students ke naam likho."

• Agar class mein 5 students hai toh jaldi ho jaayega.

• Agar 500 students hai, toh time zyada lagega.

Time lagna = kaam ka size ya input ke upar depend karta hai.

Isi cheez ko programming mein "Time Complexity" kehte hain:

"Input size badhne par, algorithm ko kitna time lagega?"

---

📏 Big O Notation (O(n), O(1), etc.)

Ye ek notation hai jo batata hai:

• Best case nahi,

• Exact time nahi,

• Balki worst-case estimate karta hai:

"Maximum kitna time lag sakta hai?"

---

🧠 1. O(1) — Constant Time

Meaning:

Jo bhi input do, time kabhi change nahi hoga.

Example:

arr[100];
cout << arr[0]; // Bas first element print karna

Input size 10 ho ya 100000, ye same speed mein chalega.

🧠 Real Life Analogy:

• Fridge mein se paani ki bottle nikaalni hai — hamesha ek hi time lagega, chahe fridge chhota ho ya bada.

---

🧠 2. O(n) — Linear Time

Meaning:

Jaise jaise input size badhega, time bhi proportionally badhega.

Example:

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

• n = 10 → 10 steps

• n = 1000 → 1000 steps

🧠 Real Life Analogy:

• Tum library mein ek book dhoond rahe ho aur har book ek ek karke check kar rahe ho.

---

🧠 3. O(log n) — Logarithmic Time

Meaning:

Input ka size har step mein aadha hota jaata hai.

Example: Binary Search

arr[] = {1,2,3,4,5,6,7,8};
int left = 0, right = 7;
while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] == key) break;
    else if (arr[mid] < key) left = mid + 1;
    else right = mid - 1;
}

🧠 Real Life Analogy:

• Tum dictionary mein "Zebra" dhoond rahe ho — tum har baar aadhi dictionary skip kar ke dekhte ho.

---

🧠 4. O(n²) — Quadratic Time

Meaning:

Do loops ek ke andar ek — jiska matlab hai har element ke liye doosre elements bhi process karne padenge.

Example:

(int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        cout << i << "," << j;
    }
}

🧠 Real Life Analogy:

• Har student ko har doosre student se handshake karna hai.

n = 3 → (3 x 3 = 9) handshakes

---

🧠 5. O(n log n) — Linearithmic Time

Meaning:

Combination of linear + log. Sorting algorithms like Merge Sort and Quick Sort use this.

Example: Merge Sort

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = (l + r) / 2;
        mergeSort(arr, l, m);         // 🔁 log n (divide)
        mergeSort(arr, m + 1, r);     // 🔁 log n (divide)
        merge(arr, l, m, r);          // 🔁 n (merge)
    }
}

🧠 Real Life Analogy:

• Tum exam papers ko pahle chhote chhote groups mein sort karte ho, fir merge karte ho.

---

🧠 6. O(2ⁿ) — Exponential Time

Meaning:

Input thoda sa bhi badhe, toh time bahut badh jaata hai.

Example: Recursive Fibonacci

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

n = 5 → 15 calls
n = 10 → 177 calls 😵‍💫
n = 30 → 2.6 crore calls 🤯

🧠 Real Life Analogy:

• Har decision par tumhe 2 choices leni ho, aur har choice par fir 2 aur choices — explosion ho jaata hai.

---

📊 Quick Comparison Chart

---

✅ Summary in 1 line:

Jitni kam time complexity, utni fast code — aur utni zyada chance ki tumhara code scale kare.