# Big-O और जटिलता — डेटा स्ट्रक्चर और एल्गोरिदम

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

> Big-O बताता है कि इनपुट बढ़ने पर समय या मेमोरी कैसे बढ़ती है।

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

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) चरण गणना लगभग...

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

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