Big-O notation کیا ہے؟

Question

IT Interview Practice · Accepted Answer

**Big-O** بیان کرتا ہے کہ جب input کا سائز **n** بڑھتا ہے تو الگورتھم کا running time یا memory کتنا بڑھتا ہے۔ یہ *worst-case* asymptotic رویے کو ظاہر کرتا ہے، constants اور lower-order terms کو نظر انداز کرتے ہوئے۔

## The idea

ہمیں exact step counts کی نہیں بلکہ growth rate کی پرواہ ہے۔ O(2n + 5) سادہ طور پر **O(n)** ہے کیونکہ جب n بہت بڑا ہو تو constants اور چھوٹی terms اہم نہیں رہتیں۔

## Common classes

| Big-O | Name | Example |
|-------|------|----------|
| O(1) | constant | array index lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scanning a list |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | nested loops |
| O(2ⁿ) | exponential | naive subsets |

## Example

```python
def has_duplicate(nums):
    for i in range(len(nums)):        # outer loop: n
        for j in range(i + 1, len(nums)):  # inner loop: n
            if nums[i] == nums[j]:
                return True
    return False
# nested loops -> O(n^2) time, O(1) space
```

## Pitfalls

Big-O constants کو چھپاتا ہے: ایک بہت بڑے constant والا O(n) الگورتھم چھوٹے inputs پر O(n log n) سے ہار سکتا ہے۔ **space** complexity کو بھی ٹریک کریں، صرف time نہیں۔

## Why it matters

Big-O آپ کو الگورتھمز کا موازنہ کرنے دیتا ہے بغیر انہیں چلائے یا hardware کی فکر کیے۔

یہ پیش گوئی کرتا ہے کہ کون سے حل اس وقت بچتے ہیں جب inputs سیکڑوں سے ملینوں تک بڑھتے ہیں — ایک feature جو scale کرے اور ایک جو timeout ہو جائے اس میں فرق۔

یہ وہ الفاظ ہیں جو ہر engineer performance کے بارے میں سوچنے کے لیے استعمال کرتا ہے۔

Big-O	Name	Example
O(1)	constant	array index lookup
O(log n)	logarithmic	binary search
O(n)	linear	scanning a list
O(n log n)	linearithmic	merge sort
O(n²)	quadratic	nested loops
O(2ⁿ)	exponential	naive subsets

The idea

Common classes

Example

Pitfalls

Why it matters

متعلقہ سوالات