Big O Notation: A-Level CS میں اصل میں کیا مطلب ہے

Big O notation ہر بڑی A-level کمپیوٹر سائنس specification (AQA, OCR, Edexcel) میں آتا ہے اور بہت سے طالب علم غلطی کرتے ہیں — نہ اس لیے کہ ریاضی مشکل ہے، بلکہ اس لیے کہ انہوں نے اسے کبھی اصل کوڈ سے جڑا ہوا نہیں دیکھا۔ یہ ایک عملی وضاحت ہے کہ آپ کو کیا جاننا ہے اور امتحان کے سوالات کے جوابات کیسے دیں بغیر بکواس کے۔

Big O اصل میں کیا ناپتا ہے

Big O بتاتا ہے کہ کسی الگورتھم کا چلنے کا وقت (یا میموری استعمال) کتنا بڑھتا ہے جب input کا سائز، عام طور پر n کہا جاتا ہے، بڑھتا ہے۔ یہ سیکنڈ میں سٹاپ واچ کی پیمائش نہیں ہے۔ یہ growth rate کو بیان کرنے کا طریقہ ہے تاکہ آپ الگورتھم کا موازنہ کر سکیں بغیر hardware کی پروا کیے۔

جب آپ O(n) لکھتے ہیں، تو آپ کہہ رہے ہیں: اگر میں input کو دوگنا کروں، تو کام تقریباً دوگنا ہو جاتا ہے۔ O(n²) کا مطلب ہے input کو دوگنا کرنے سے کام تقریباً چار گنا ہو جاتا ہے۔ یہ رشتہ ہے جو معلمین آپ سے شناخت کرنا چاہتے ہیں، نہ کہ operations کی بالکل درست تعداد۔

Complexities جو آپ کو یقیناً معلوم ہونی چاہئیں

A-level کے لیے، یہ وہ ہیں جو بار بار آتے ہیں:

• O(1) – constant time۔ Array element کو index سے access کرنا: arr[5]۔ Array کتنا بھی بڑا ہو، کوئی فرق نہیں۔
• O(log n) – logarithmic۔ Sorted list میں binary search۔ ہر مرحلہ باقی search space کو آدھا کرتا ہے۔
• O(n) – linear۔ List کے ذریعے ایک loop، جیسے linear search جو ہر item کو ایک بار check کرتا ہے۔
• O(n log n) – linearithmic۔ Merge sort اور quicksort (average case) یہاں آتے ہیں۔
• O(n²) – quadratic۔ Nested loops ایک ہی data پر، جو بالکل وہی ہے جو bubble sort، insertion sort، اور selection sort کرتے ہیں۔
• O(2ⁿ) – exponential۔ Naive recursive Fibonacci بغیر memoisation کے۔ جلدی بہت خراب ہو جاتا ہے۔

آپ کو pseudocode دیکھتے ہی یہ کہنے کے قابل ہونا چاہیے کہ یہ کون سا ہے، کیونکہ یہی زیادہ تر test ہوتا ہے۔

Complexity کے لیے کوڈ پڑھنا

جو طریقہ ہمیشہ کام کرتا ہے: loops کو گنیں اور دیکھیں کہ وہ n سے کیسے جڑے ہوئے ہیں۔

# O(n) - ایک loop، ایک pass
for i in range(n):
    print(i)

# O(n^2) - nested loop، دونوں n سے جڑے ہیں
for i in range(n):
    for j in range(n):
        print(i, j)

# O(log n) - search space ہر iteration میں آدھا ہو جاتا ہے
low, high = 0, n - 1
while low <= high:
    mid = (low + high) // 2
    if target == arr[mid]:
        break
    elif target < arr[mid]:
        high = mid - 1
    else:
        low = mid + 1

Nested loop جہاں inner loop کی range n پر منحصر ہے، وہ بھی O(n²) ہے، یہاں تک کہ اگر یہ تھوڑا مختلف نظر آئے (for j in range(i) کی بجائے for j in range(n) — یہ ابھی بھی quadratic ہے مجموعی طور پر، صرف constant factor فرق کے ساتھ)۔

ایسے loops سے ساویل رہیں جو بالکل n پر منحصر نہیں ہیں۔ ایک loop جو ہمیشہ 10 بار چلتا ہے قطع نظر input size کے، وہ O(1) ہے، اگرچہ ایک loop موجود ہے۔ معلمین اسے چھپ کر ڈالنا پسند کرتے ہیں۔

عام sorting algorithms اور ان کا Big O

یہ ایک پسندیدہ امتحان کا موضوع ہے کیونکہ یہ دو specs کو ملاتا ہے: sorting algorithms اور complexity۔

Algorithm	Best case	Worst case
Bubble sort	O(n)	O(n²)
Insertion sort	O(n)	O(n²)
Merge sort	O(n log n)	O(n log n)
Binary search	O(1)	O(log n)
Linear search	O(1)	O(n)

Merge sort کی consistency (best اور worst case میں ایک جیسی complexity) قابل غور ہے اگر کوئی سوال پوچھے کہ بڑے datasets کے لیے آپ اسے bubble sort سے زیادہ کیوں منتخب کریں گے۔ Bubble sort کا best case O(n) صرف early-exit optimization کے ساتھ لاگو ہوتا ہے جب ایک pass میں کوئی swaps نہ ہوں — اگر آپ یہ بات اٹھاتے ہیں تو یہ تفصیل بتائیں، کیونکہ کچھ exam boards اسے توقع کرتے ہیں۔

جہاں طالب علم نمبر کھوتے ہیں

سب سے بڑا: لکھنا