# Big-O और जटिलता — Data Structures और Algorithms: Interviews के लिए Patterns

Source: https://www.skillbyai.com/hi/dsa/big-o

> Input size के साथ running time और memory कैसे बढ़ते हैं यह बताने के लिए Big-O notation सीखें, आम complexity classes के साथ।

## वृद्धि, स्टॉपवॉच नहीं

Big-O स्थिरांक और मशीन गति को अनदेखा करके पूछता है: **यदि इनपुट दोगुना हो, तो काम का क्या होगा?** `O(1)` अपरिवर्तित, `O(log n)` एक चरण बढ़ता है, `O(n)` दोगुना, `O(n log n)` दोगुने से थोड़ा अधिक, `O(n^2)` चौगुना।

## लूप से जटिलता पढ़ना

`n` वस्तुओं पर एक बार गुज़रना `O(n)` है। एक ही डेटा पर लूप के अंदर लूप `O(n^2)` है। हर चरण में सीमा आधी करना `O(log n)` है।

```python
for x in arr:            # O(n)
    print(x)

for i in arr:            # O(n^2)
    for j in arr:
        print(i, j)

lo, hi = 0, len(arr) - 1 # O(log n)
while lo <= hi:
    mid = (lo + hi) // 2
    ...
```

## समय बनाम स्थान

स्थान जटिलता इनपुट से परे *अतिरिक्त* मेमोरी गिनती है — कुछ वेरिएबल `O(1)`, array की प्रति `O(n)`, `n` गहराई की recursion `O(n)` स्टैक स्थान। इंटरव्यूअर अक्सर एक को दूसरे से बदलने को कहते हैं।

**Quiz:** इनपुट 1,000 से 1,000,000 हो जाता है। O(log n) चरण गणना लगभग...

- [ ] तीन गुना
- [ ] 1000 गुना बढ़ती है
- [x] ~10 चरण बढ़ती है
- [ ] दोगुना होता है

*Answer:* ~10 चरण बढ़ती है. log2(1e6) - log2(1e3) लगभग 20 - 10 = 10 अतिरिक्त चरण।