Asymptotic Notation — বৃদ্ধির হারের ভাষা

আগে এটা বুঝি

দুইটা function। দুটোই সঠিক উত্তর দেয়। কোনটা ভালো?

def has_duplicate_a(items):
    for i in range(len(items)):
        for j in range(i+1, len(items)):
            if items[i] == items[j]: return True
    return False

def has_duplicate_b(items):
    return len(set(items)) != len(items)

“চালিয়ে দেখি” যথেষ্ট নয় — আপনার মেশিনে, আপনার input-এ, আজকের load-এ যা দ্রুত, সেটা অন্য কোথাও উল্টো হতে পারে।

দরকার একটা ভাষা যা মেশিন-নিরপেক্ষ, আর যা প্রশ্নটা এভাবে করে: input দ্বিগুণ করলে কাজ কতগুণ বাড়বে?

সেই ভাষাটাই asymptotic notation।

has_duplicate_a Θ(n²) — input দ্বিগুণে কাজ চারগুণ। has_duplicate_b গড়ে Θ(n) — দ্বিগুণে দ্বিগুণ।

n = 100-এ পার্থক্য নগণ্য। n = 1,000,000-এ প্রথমটা কখনো শেষ হবে না।

কিন্তু এই লেসনের দ্বিতীয়ার্ধটা সমান গুরুত্বপূর্ণ: এই বিমূর্তকরণটা কোথায় মিথ্যা বলে। গত লেসনেই আমরা দেখেছি দুইটা Θ(n³) matrix multiply-এর মধ্যে তিন গুণ সময়ের পার্থক্য — হুবহু একই FLOP সংখ্যায়।

মূল ধারণা

আনুষ্ঠানিক সংজ্ঞা

Predicate logic-এর লেসনের quantifier এখানে সরাসরি কাজে লাগে।

Big O — উপরের সীমা

$f(n) = O(g(n)) \iff \exists c > 0, \exists n_0 : \forall n \ge n_0,\; f(n) \le c\,g(n)$

সাধারণ ভাষায়: “যথেষ্ট বড় n-এর জন্য, একটা ধ্রুবক গুণক বাদে f কখনো g-এর চেয়ে বড় হয় না।”

দুইটা শব্দ গুরুত্বপূর্ণ: n₀ (ছোট n-এর আচরণ অগ্রাহ্য) আর c (ধ্রুবক গুণক অগ্রাহ্য)।

Big Omega — নিচের সীমা

$f(n) = \Omega(g(n)) \iff \exists c > 0, \exists n_0 : \forall n \ge n_0,\; f(n) \ge c\,g(n)$

Big Theta — আঁটসাঁট সীমা

$f(n) = \Theta(g(n)) \iff f(n) = O(g(n)) \text{ এবং } f(n) = \Omega(g(n))$

দুই দিক থেকেই বাঁধা — এটাই সবচেয়ে তথ্যবহুল দাবি।

ছোট o এবং ω — কঠোর সীমা

$f(n) = o(g(n)) \iff \forall c > 0, \exists n_0 : \forall n \ge n_0,\; f(n) \lt c\,g(n)$

O বলে “এর চেয়ে বেশি নয়”; o বলে “এর চেয়ে কঠোরভাবে কম”। n = O(n) সত্য, কিন্তু n = o(n) মিথ্যা।

সংকেত	অর্থ	সংখ্যার সাদৃশ্য
`f = O(g)`	`f` বড়জোর `g`	`≤`
`f = Ω(g)`	`f` অন্তত `g`	`≥`
`f = Θ(g)`	`f` ঠিক `g`-এর মতো	`=`
`f = o(g)`	`f` কঠোরভাবে ছোট	`\<`
`f = ω(g)`	`f` কঠোরভাবে বড়	`>`

পাঁচটা সংকেতের সম্পর্ক — সংখ্যার তুলনার সাথে মিলিয়ে মনে রাখা সহজ।

`O` -এর সবচেয়ে সাধারণ অপব্যবহার

O একটা উপরের সীমা, তাই এগুলো সবই সত্য:

n     = O(n)
n     = O(n²)
n     = O(n³)
n     = O(2ⁿ)

সবগুলোই সত্য, কিন্তু শেষ তিনটা অকেজো — যেমন “আমার বয়স ১০০০ বছরের কম” বলাটা সত্য কিন্তু তথ্যহীন।

মানুষ O(n log n) বলে যখন আসলে Θ(n log n) বোঝায়। প্রচলনে এটা মেনে নেওয়া হয়েছে, কিন্তু পার্থক্যটা জানা জরুরি — বিশেষত যখন কেউ lower bound নিয়ে কথা বলছে।

“Quicksort O(n²)” — সত্য (worst case)। “Quicksort Θ(n²)” — মিথ্যা (average Θ(n log n))।

বৃদ্ধির হারের সোপান

জটিলতা	নাম	`n=10`	`n=100`	`n=10⁶`
`O(1)`	ধ্রুবক	1	1	1
`O(log n)`	লগারিদমিক	3	7	20
`O(√n)`	মূল	3	10	1,000
`O(n)`	রৈখিক	10	100	10⁶
`O(n log n)`	linearithmic	33	664	2×10⁷
`O(n²)`	বর্গীয়	100	10⁴	10¹²
`O(n³)`	ঘনীয়	1,000	10⁶	10¹⁸
`O(2ⁿ)`	সূচকীয়	1,024	10³⁰	—
`O(n!)`	ক্রমিক	3.6×10⁶	10¹⁵⁸	—

সেকেন্ডে 10⁹ operation ধরে বাস্তব সময়:

জটিলতা	`n = 10⁶`	`n = 10⁹`
`O(n)`	১ ms	১ সেকেন্ড
`O(n log n)`	২০ ms	৩০ সেকেন্ড
`O(n²)`	১৭ মিনিট	৩২ বছর
`O(n³)`	৩২ বছর	—

n² আর n log n-এর মধ্যেই সবচেয়ে গুরুত্বপূর্ণ সীমারেখা। বেশিরভাগ বাস্তব সমস্যায় O(n²) মানে “১০ লক্ষ পর্যন্ত চলবে, তার বেশি নয়”।

সরলীকরণের নিয়ম

১. ধ্রুবক গুণক বাদ: 5n² = Θ(n²)

২. নিম্নক্রমের পদ বাদ: 3n² + 100n + 5000 = Θ(n²)

কেন বৈধ — কারণ n → ∞-এ: $\lim_{n\to\infty} \frac{3n^2 + 100n + 5000}{n^2} = 3$

একটা ধ্রুবকে স্থিতিশীল, তাই Θ(n²)।

৩. সবচেয়ে দ্রুতবর্ধমান পদই থাকে: n log n + n = Θ(n log n)

৪. পরপর block যোগ, nested loop গুণ:

for i in range(n): ...        # Θ(n)
for j in range(n): ...        # Θ(n)      →  Θ(n) + Θ(n) = Θ(n)

for i in range(n):
    for j in range(n): ...    # Θ(n) × Θ(n) = Θ(n²)

এটা combinatorics-এর sum rule আর product rule — সরাসরি।

Loop বিশ্লেষণ

i = n
while i > 1:
    i = i // 2          # Θ(log n) — প্রতিবার অর্ধেক

for i in range(n):
    for j in range(i):  # 0 + 1 + 2 + ⋯ + (n−1) = n(n−1)/2
        ...             # Θ(n²)

দ্বিতীয়টায় লক্ষ্য করুন ভেতরের loop-এর সীমা বদলাচ্ছে — তবু যোগফলটা Θ(n²)। ধ্রুবক 1/2 বাদ যায়।

i = 1
while i \< n:
    for j in range(n): ...
    i *= 2              # Θ(n log n)

বাইরের loop log n বার, ভেতরেরটা n বার।

Recurrence আর Master Theorem

Induction-এর লেসনে আমরা merge sort-এর T(n) = 2T(n/2) + Θ(n) হাতে প্রমাণ করেছি। Master Theorem সেই কাজটার শর্টকাট।

$T(n) = a\,T(n/b) + f(n), \qquad a \ge 1,\; b > 1$

n^(log_b a) -এর সাথে f(n) তুলনা করুন:

ক্ষেত্র	শর্ত	ফল
১	`f(n) = O(n^{log_b a − ε})`	`T(n) = Θ(n^{log_b a})`
২	`f(n) = Θ(n^{log_b a})`	`T(n) = Θ(n^{log_b a} log n)`
৩	`f(n) = Ω(n^{log_b a + ε})` ও regularity	`T(n) = Θ(f(n))`

স্বজ্ঞা: গাছের পাতায় বেশি কাজ (ক্ষেত্র ১), সব স্তরে সমান (ক্ষেত্র ২), নাকি মূলে বেশি (ক্ষেত্র ৩)।

উদাহরণ ১ — Binary search: T(n) = T(n/2) + Θ(1)

a=1, b=2 → n^(log₂ 1) = n⁰ = 1। f(n) = Θ(1) = Θ(1)। ক্ষেত্র ২ → T(n) = Θ(log n)

উদাহরণ ২ — Merge sort: T(n) = 2T(n/2) + Θ(n)

a=2, b=2 → n^(log₂ 2) = n। f(n) = Θ(n)। ক্ষেত্র ২ → T(n) = Θ(n log n)

Induction-এর লেসনে যেটা এক পাতা লেগেছিল, এখানে দুই লাইন।

উদাহরণ ৩ — ক্ষেত্র ৩: T(n) = 2T(n/2) + Θ(n²)

n^(log₂ 2) = n, আর f(n) = Θ(n²) = Ω(n^{1+1})। ক্ষেত্র ৩ → T(n) = Θ(n²)

মূলের কাজই প্রাধান্য পায়।

Amortised analysis

কিছু operation মাঝে মাঝে ব্যয়বহুল, কিন্তু গড়ে সস্তা।

Dynamic array (list.append) — সবচেয়ে গুরুত্বপূর্ণ উদাহরণ।

Array ভরে গেলে দ্বিগুণ আকারের নতুন array বানিয়ে সব copy করতে হয় — সেই একটা append Θ(n)। বাকিগুলো Θ(1)।

Aggregate method: n টা append-এ মোট কত কাজ?

Resize ঘটে n = 1, 2, 4, 8, … -এ, আর প্রতিবার copy খরচ সেই আকারের সমান:

$1 + 2 + 4 + \cdots + 2^{\lfloor \log_2 n \rfloor} \lt 2n$

Geometric series — যোগফল 2n-এর কম।

মোট কাজ = n টা append + 2n-এর কম copy = 3n-এর কম।

$\text{amortised খরচ} = \frac{3n}{n} = \Theta(1)$

প্রতিটা append গড়ে ধ্রুবক সময়, যদিও কিছু append Θ(n)।

কেন দ্বিগুণ, ১ যোগ নয়

যদি প্রতিবার আকার ১ বাড়ানো হতো:

$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} = \Theta(n^2)$

Amortised খরচ Θ(n) — বিপর্যয়।

Growth factor-এর trade-off:

Factor	মোট copy	অপচয়ী জায়গা
2	`< 2n`	সর্বোচ্চ ৫০%
1.5	`< 3n`	সর্বোচ্চ ৩৩%

দুটোই Θ(1) amortised। কিন্তু 1.5 কম memory অপচয় করে, আর মুক্ত হওয়া block পুনর্ব্যবহার করা সহজ করে।

CPython list প্রায় 1.125× বাড়ায় (আরো সূক্ষ্ম সূত্র), Java-র ArrayList 1.5×, C++ std::vector সাধারণত 2× (libstdc++) বা 1.5× (MSVC)।

Amortised ≠ worst case। একটা real-time audio loop-এ সেই একটা Θ(n) resize একটা শ্রবণযোগ্য glitch তৈরি করতে পারে। তখন আগেই reserve() করে রাখুন।

দুইটা আলাদা অক্ষ — এটা গুলিয়ে ফেলবেন না

এটা সবচেয়ে সাধারণ বিভ্রান্তি।

অক্ষ ১ — কোন input: best case, average case, worst case

অক্ষ ২ — কোন সীমা: O, Ω, Θ

দুইটা স্বাধীন। যেকোনো combination সম্ভব।

Quicksort-এর জন্য:

	Best	Average	Worst
Θ	`Θ(n log n)`	`Θ(n log n)`	`Θ(n²)`
O	`O(n log n)`	`O(n log n)`	`O(n²)`
Ω	`Ω(n log n)`	`Ω(n log n)`	`Ω(n²)`

তাই “quicksort-এর worst case-এর Ω” একটা সম্পূর্ণ অর্থবহ প্রশ্ন — উত্তর Ω(n²)।

নিয়ম: আগে বলুন কোন input (best/average/worst), তারপর কোন সীমা (O/Ω/Θ)।

ভেতরে কী ঘটছে

যেখানে asymptotic analysis মিথ্যা বলে

এই অংশটাই এই লেসনের সবচেয়ে গুরুত্বপূর্ণ।

১. ধ্রুবক বাস্তবে গুরুত্বপূর্ণ

Insertion sort Θ(n²), merge sort Θ(n log n)। তবু ছোট n-এ insertion sort দ্রুত:

কোনো recursion overhead নেই
কোনো বাড়তি memory allocation নেই
Sequential memory access — cache-friendly
Branch predictor ভালো কাজ করে

তাই প্রতিটা বাস্তব sort implementation একটা threshold রাখে:

Library	Threshold
Python (Timsort)	64 (minrun)
C++ `std::sort` (introsort)	16
Java `Arrays.sort`	47

এগুলো তাত্ত্বিক সংখ্যা নয় — measure করে বের করা।

২. Cache locality — সবচেয়ে বড় মিথ্যা

Linked list traversal আর array traversal দুটোই Θ(n)। বাস্তবে array ১০–৫০ গুণ দ্রুত।

কারণ:

Array — sequential memory, প্রতি cache line-এ ৮–১৬টা element, prefetcher কাজ করে
Linked list — প্রতিটা node ভিন্ন জায়গায়, প্রতিটা access একটা cache miss, prefetcher অসহায়

Array:        [a][b][c][d][e][f][g][h]  ← একটা cache line
              prefetcher পরেরটা আগেই আনে

Linked list:  [a]→ ...দূরে... [b]→ ...দূরে... [c]
              প্রতিবার নতুন cache line, ~100 cycle অপেক্ষা

একই complexity, ভিন্ন বাস্তবতা — memory hierarchy asymptotic analysis-এ অদৃশ্য।

গত লেসনের matrix multiply experiment-এ আমরা এটা মেপেছি — একই FLOP, তিন গুণ সময়।

৩. Galactic algorithm

কিছু algorithm asymptotically ভালো কিন্তু ধ্রুবক এত বিশাল যে কখনো ব্যবহার করা যায় না।

Matrix multiplication:

Algorithm	Exponent	ব্যবহারিক?
Naive	`n³`	হ্যাঁ
Strassen (1969)	`n^2.807`	`n > ~1000`-এ হ্যাঁ
Coppersmith–Winograd শ্রেণি	`n^2.37`	কখনো না

শেষেরটার ধ্রুবক এত বড় যে crossover point মহাবিশ্বে আঁটে এমন কোনো matrix-এর চেয়ে বড়। একে বলে galactic algorithm।

৪. Memory hierarchy asymptotics বদলে দেয়

Hash table O(1) lookup, B-tree O(log n)। তাহলে hash table সবসময় ভালো?

ডিস্কে নয়। সেখানে খরচ CPU cycle নয়, disk seek:

	Hash (disk)	B-tree (disk)
Lookup	১ random seek	২–৪ seek (উপরের level cached)
Range query	অসম্ভব	sequential scan
Sorted order	নেই	আছে

আর এজন্যই প্রতিটা relational database-এর default index B-tree, hash নয়। O(log n) জিতে যায় কারণ ধ্রুবকটা সম্পূর্ণ ভিন্ন জিনিস মাপছে।

৫. Amortised বনাম tail latency

Θ(1) amortised মানে গড়ে ধ্রুবক — কিন্তু একটা নির্দিষ্ট operation Θ(n) হতে পারে।

Latency-সংবেদনশীল সিস্টেমে এই spike-টাই সমস্যা:

Real-time audio — একটা resize = শ্রবণযোগ্য click
Game loop — একটা GC pause = frame drop
Trading system — একটা rehash = মিস করা সুযোগ

তাই এসব জায়গায় reserve() করে রাখা হয়, বা incremental resize করা হয় (একবারে সব copy না করে ধীরে ধীরে)।

একটা 'O(1)' lookup আসলে কী কী স্পর্শ করে

hash_table[key]তাত্ত্বিকভাবে O(1)
hash গণনাkey-এর দৈর্ঘ্যের সমানুপাতিক — O(1) নয়!
bucket index% বা & — কয়েক cycle
L1 cache lookup~4 cycle যদি hit
L2 / L3~14 / ~40 cycle
DRAM~200 cycle — L1-এর ৫০ গুণ
Page fault → disk~100,000 cycle

উপর থেকে নিচে ৫ মাত্রার পার্থক্য — আর asymptotic notation-এ এর কিছুই দেখা যায় না।

উপসংহার: asymptotic analysis যেখানে আপনি শুরু করেন, যেখানে শেষ করেন সেখানে নয়। এটা বলে কোন algorithm scale করবে; measurement বলে কোনটা আসলে দ্রুত।

Level 11-এ পুরোটাই measurement নিয়ে।

উদাহরণ

একটা সম্পূর্ণ বিশ্লেষণ

def find_pairs(items, target):
    """যোগফল target এমন সব জোড়া"""
    seen = set()
    out = []
    for x in items:                     # n বার
        if target - x in seen:          # গড়ে O(1)
            out.append((target - x, x))
        seen.add(x)                     # গড়ে O(1)
    return out

Time:

Loop n বার
প্রতিবার: set lookup + set insert, দুটোই average Θ(1)
Average: Θ(n)
Worst: Θ(n²) — সব key যদি একই bucket-এ collide করে

Space: seen সর্বোচ্চ n element → Θ(n)

তুলনায় naive:

def find_pairs_naive(items, target):
    out = []
    for i in range(len(items)):
        for j in range(i+1, len(items)):
            if items[i] + items[j] == target:
                out.append((items[i], items[j]))
    return out

Θ(n²) time, Θ(1) extra space।

এটাই time–space trade-off: hash-ভিত্তিক পদ্ধতি Θ(n) memory খরচ করে Θ(n²) থেকে Θ(n) সময়ে নামায়।

n = 10⁶-এ:

Naive: 5×10¹¹ operation ≈ ৮ মিনিট
Hash: 10⁶ operation ≈ কয়েক মিলিসেকেন্ড, কিন্তু ~৫০ MB memory

Memory যদি সীমিত হয় (embedded system), naive-টাই সঠিক পছন্দ।

Space complexity — যা প্রায়ই ভুলে যাওয়া হয়

def sum_recursive(n):
    if n == 0: return 0
    return n + sum_recursive(n - 1)

Time Θ(n), কিন্তু space-ও Θ(n) — কারণ n টা stack frame।

def sum_iterative(n):
    total = 0
    for i in range(1, n+1): total += i
    return total

Time Θ(n), space Θ(1)।

Induction-এর লেসনে আমরা দেখেছি n যথেষ্ট বড় হলে প্রথমটা stack overflow করে — 8 MB stack-এ প্রায় ২,৬০,০০০ frame।

Space-এর তিনটা ভাগ:

ভাগ	উদাহরণ
Input space	parameter নিজে
Auxiliary space	algorithm-এর নিজের বরাদ্দ
Stack space	recursion depth

সাধারণত “space complexity” বলতে auxiliary + stack বোঝানো হয়।

Merge sort Θ(n) auxiliary space লাগে (merge buffer), তাই in-place নয়। Heapsort Θ(1) auxiliary — সেজন্য memory-সীমিত পরিবেশে heapsort পছন্দনীয়, যদিও cache locality খারাপ।

নিজে চালিয়ে দেখুন

EXPERIMENT

Timing থেকে exponent উদ্ধার করুন

Python 3· ১৫ মিনিট

Input দ্বিগুণ করলে:

Complexity	`t(2n)/t(n)`
`O(1)`	1.0
`O(log n)`	~1.1
`O(n)`	2.0
`O(n log n)`	~2.1–2.2
`O(n²)`	4.0
`O(n³)`	8.0

import time, random

def linear(n):
    data = list(range(n))
    return sum(data)

def n_log_n(n):
    data = [random.random() for _ in range(n)]
    return sorted(data)[0]

def quadratic(n):
    data = list(range(n))
    c = 0
    for i in range(n):
        for j in range(n):
            c += 1
    return c

def logarithmic(n):
    data = list(range(n))
    lo, hi, target = 0, n, n - 1
    while lo \< hi:
        mid = (lo + hi) // 2
        if data[mid] \< target: lo = mid + 1
        else: hi = mid
    return lo


def measure(fn, n, repeats=3):
    best = float('inf')
    for _ in range(repeats):
        t0 = time.perf_counter()
        fn(n)
        best = min(best, time.perf_counter() - t0)
    return best


def profile(fn, sizes, name):
    print(f"\n{name}")
    print(f"  {'n':>9} {'time (ms)':>12} {'t(2n)/t(n)':>12}")
    prev = None
    for n in sizes:
        t = measure(fn, n)
        ratio = f"{t/prev:.2f}" if prev else "—"
        print(f"  {n:>9,} {t*1000:>12.3f} {ratio:>12}")
        prev = t

profile(logarithmic, [10**4, 2*10**4, 4*10**4, 8*10**4], "binary search — আশা ~1.0")
profile(linear,      [10**5, 2*10**5, 4*10**5, 8*10**5], "sum — আশা 2.0")
profile(n_log_n,     [10**5, 2*10**5, 4*10**5, 8*10**5], "sorted — আশা ~2.1")
profile(quadratic,   [1000, 2000, 4000],                  "nested loop — আশা 4.0")

সাধারণ ফলাফল:

sum — আশা 2.0
          n    time (ms)   t(2n)/t(n)
    100,000        1.842            —
    200,000        3.701         2.01
    400,000        7.428         2.01
    800,000       14.901         2.01

nested loop — আশা 4.0
          n    time (ms)   t(2n)/t(n)
      1,000       23.104            —
      2,000       92.318         4.00
      4,000      369.442         4.00

অনুপাতগুলো তাত্ত্বিক মানের সাথে চমৎকার মিলে যায়।

sorted-এর অনুপাত ২.১-এর কাছাকাছি — 2 + 2/log₂n, যা n = 10⁵-এ প্রায় 2.12।

logarithmic-এ অনুপাত ~1.0, কিন্তু সংখ্যাগুলো এত ছোট যে noise বেশি — এটাও একটা শিক্ষা: খুব দ্রুত operation measure করা কঠিন, timer resolution আর overhead ফলাফল ঢেকে দেয়।

এটা কী প্রমাণ করে

Input দ্বিগুণ করে সময়ের অনুপাত দেখলে complexity class সরাসরি বেরিয়ে আসে — তাত্ত্বিক দাবিটা পরীক্ষামূলকভাবে যাচাই করা যায়।

EXPERIMENT

যেখানে Big-O মিথ্যা বলে — cache locality

Python 3, বা C· ১৫ মিনিট

import time, random

def build_sequential(n):
    """index i থেকে i+1 — sequential"""
    return list(range(1, n)) + [0]

def build_random(n):
    """একটা random permutation cycle — pointer chasing"""
    perm = list(range(n))
    random.shuffle(perm)
    nxt = [0] * n
    for i in range(n - 1):
        nxt[perm[i]] = perm[i + 1]
    nxt[perm[-1]] = perm[0]
    return nxt

def traverse(nxt, n):
    """ঠিক n ধাপ — দুই ক্ষেত্রেই একই কাজ"""
    i, total = 0, 0
    for _ in range(n):
        total += i
        i = nxt[i]
    return total


print(f"{'n':>10} {'sequential':>14} {'random':>12} {'অনুপাত':>9}")
print("─" * 50)
for n in [10**4, 10**5, 10**6, 4*10**6]:
    seq, rnd = build_sequential(n), build_random(n)

    t0 = time.perf_counter(); traverse(seq, n); t_seq = time.perf_counter() - t0
    t0 = time.perf_counter(); traverse(rnd, n); t_rnd = time.perf_counter() - t0

    print(f"{n:>10,} {t_seq*1000:>12.1f}ms {t_rnd*1000:>10.1f}ms "
          f"{t_rnd/t_seq:>8.2f}×")

সাধারণ ফলাফল:

         n     sequential       random    অনুপাত
──────────────────────────────────────────────────
    10,000          1.2ms        1.3ms     1.08×
   100,000         12.4ms       15.8ms     1.27×
 1,000,000        126.1ms      271.3ms     2.15×
 4,000,000        512.7ms     1783.4ms     3.48×

দুইটাই ঠিক n ধাপ। একই সংখ্যক array access, একই সংখ্যক যোগ। তবু বড় n-এ ৩.৫ গুণ পার্থক্য।

আর লক্ষ্য করুন পার্থক্যটা n-এর সাথে বাড়ছে — কারণ ছোট n-এ পুরো array cache-এ আঁটে, তাই access pattern অপ্রাসঙ্গিক। Array যখন L3 cache ছাড়িয়ে যায়, তখনই random access-এর দাম শুরু।

C-তে পার্থক্য অনেক বড় (Python-এর interpreter overhead memory effect ঢেকে দেয়):

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

double bench(int *next, size_t n) {
    size_t i = 0; long long total = 0;
    clock_t t = clock();
    for (size_t s = 0; s \< n; s++) { total += i; i = next[i]; }
    double dt = (double)(clock() - t) / CLOCKS_PER_SEC;
    if (total == -1) printf("");        /* optimize-away ঠেকাতে */
    return dt;
}

int main(void) {
    size_t n = 16 * 1024 * 1024;        /* ~64 MB — cache ছাড়িয়ে */
    int *seq = malloc(n * sizeof(int));
    int *rnd = malloc(n * sizeof(int));
    int *perm = malloc(n * sizeof(int));

    for (size_t i = 0; i \< n; i++) { seq[i] = (i + 1) % n; perm[i] = i; }
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = rand() % (i + 1);
        int t = perm[i]; perm[i] = perm[j]; perm[j] = t;
    }
    for (size_t i = 0; i \< n - 1; i++) rnd[perm[i]] = perm[i + 1];
    rnd[perm[n-1]] = perm[0];

    printf("sequential : %6.3f s\n", bench(seq, n));
    printf("random     : %6.3f s\n", bench(rnd, n));
    return 0;
}

gcc -O2 -o chase chase.c && ./chase

সাধারণত ১০–২০ গুণ পার্থক্য।

কেন: sequential access-এ hardware prefetcher pattern চিনে পরের cache line আগেই এনে রাখে। Random access-এ prefetcher অসহায় — প্রতিটা access একটা পূর্ণ DRAM latency (~২০০ cycle, L1-এর ~৫০ গুণ)।

perf দিয়ে সরাসরি দেখুন:

perf stat -e cache-misses,cache-references,cycles ./chase

এটা কী প্রমাণ করে

দুইটা Θ(n) traversal-এর মধ্যে ১০ গুণের বেশি পার্থক্য হতে পারে, শুধু memory access pattern-এর কারণে। Asymptotic notation-এ এটা সম্পূর্ণ অদৃশ্য।

নিজে বানান

BUILD IT

Empirical Complexity Estimator

Python · ●●●○○

একটা function-কে বিভিন্ন input size-এ চালিয়ে সময় মাপুন
log t বনাম log n -এ একটা সরলরেখা fit করে exponent বের করুন
প্রার্থী complexity class-এর সাথে মিলিয়ে সবচেয়ে ভালোটা বলুন
পরিচিত function-এ চালিয়ে যাচাই করুন সেটা সঠিক class ধরতে পারে

মূল ধারণা: যদি t = c·nᵏ, তাহলে log t = log c + k·log n — একটা সরলরেখা যার ঢাল k।

import time, math, random, statistics


def measure(fn, n, repeats=5):
    """সবচেয়ে দ্রুত run নিন — noise কমাতে"""
    best = float('inf')
    for _ in range(repeats):
        setup = fn.setup(n) if hasattr(fn, 'setup') else n
        t0 = time.perf_counter()
        fn(setup)
        best = min(best, time.perf_counter() - t0)
    return best


def fit_exponent(sizes, times):
    """log-log regression → ঢাল = exponent"""
    xs = [math.log(n) for n in sizes]
    ys = [math.log(t) for t in times]
    mx, my = statistics.fmean(xs), statistics.fmean(ys)
    num = sum((x-mx)*(y-my) for x, y in zip(xs, ys))
    den = sum((x-mx)**2 for x in xs)
    slope = num / den
    # R² — fit কতটা ভালো
    pred = [my + slope*(x-mx) for x in xs]
    ss_res = sum((y-p)**2 for y, p in zip(ys, pred))
    ss_tot = sum((y-my)**2 for y in ys)
    r2 = 1 - ss_res/ss_tot if ss_tot else 1.0
    return slope, r2


CANDIDATES = [
    ("O(1)",        lambda n: 1.0),
    ("O(log n)",    lambda n: math.log(n)),
    ("O(n)",        lambda n: n),
    ("O(n log n)",  lambda n: n * math.log(n)),
    ("O(n²)",       lambda n: n**2),
    ("O(n³)",       lambda n: n**3),
]

def best_class(sizes, times):
    """প্রতিটা প্রার্থীর জন্য t/f(n) কতটা স্থির দেখুন"""
    scored = []
    for name, f in CANDIDATES:
        ratios = [t / f(n) for n, t in zip(sizes, times)]
        m = statistics.fmean(ratios)
        if m == 0: continue
        cv = statistics.pstdev(ratios) / m      # coefficient of variation
        scored.append((cv, name))
    scored.sort()
    return scored


def analyse(fn, sizes, name, repeats=5):
    times = [measure(fn, n, repeats) for n in sizes]
    slope, r2 = fit_exponent(sizes, times)
    scored = best_class(sizes, times)

    print(f"\n{'═'*58}")
    print(f"  {name}")
    print(f"{'═'*58}")
    print(f"  {'n':>9} {'time (ms)':>12} {'ratio':>8}")
    prev = None
    for n, t in zip(sizes, times):
        r = f"{t/prev:.2f}" if prev else "—"
        print(f"  {n:>9,} {t*1000:>12.3f} {r:>8}")
        prev = t
    print(f"\n  log-log ঢাল : {slope:.3f}   (R² = {r2:.4f})")
    print(f"  সেরা মিল    : {scored[0][1]}  (cv = {scored[0][0]:.3f})")
    print(f"  দ্বিতীয়     : {scored[1][1]}  (cv = {scored[1][0]:.3f})")


# ── পরীক্ষার function ────────────────────────────────────────
def f_linear(n):
    return sum(range(n))

def f_quadratic(n):
    c = 0
    for i in range(n):
        for j in range(n): c += 1
    return c

def f_sort(data):
    return sorted(data)
f_sort.setup = lambda n: [random.random() for _ in range(n)]

def f_binary_search(data):
    lo, hi = 0, len(data)
    target = len(data) - 1
    while lo \< hi:
        mid = (lo + hi) // 2
        if data[mid] \< target: lo = mid + 1
        else: hi = mid
    return lo
f_binary_search.setup = lambda n: list(range(n))


analyse(f_linear,        [10**5, 2*10**5, 4*10**5, 8*10**5], "sum(range(n)) — আশা O(n)")
analyse(f_sort,          [10**5, 2*10**5, 4*10**5, 8*10**5], "sorted() — আশা O(n log n)")
analyse(f_quadratic,     [500, 1000, 2000, 4000],            "nested loop — আশা O(n²)")
analyse(f_binary_search, [10**4, 10**5, 10**6, 10**7],       "binary search — আশা O(log n)")

প্রত্যাশিত আউটপুট (সংক্ষিপ্ত):

  sum(range(n)) — আশা O(n)
  log-log ঢাল : 1.002   (R² = 0.9999)
  সেরা মিল    : O(n)  (cv = 0.004)

  sorted() — আশা O(n log n)
  log-log ঢাল : 1.061   (R² = 0.9997)
  সেরা মিল    : O(n log n)  (cv = 0.012)

  nested loop — আশা O(n²)
  log-log ঢাল : 1.998   (R² = 1.0000)
  সেরা মিল    : O(n²)  (cv = 0.002)

লক্ষ্য করুন sorted()-এর ঢাল 1.06 — n আর n log n-এর মাঝামাঝি, ঠিক যেমন হওয়ার কথা। তাই শুধু ঢাল যথেষ্ট নয়; coefficient of variation দিয়ে প্রার্থী মেলানোটাই বেশি নির্ভরযোগ্য।

নিজে বাড়ান:

Best/average/worst case আলাদা করে মাপুন — quicksort-এ sorted input দিয়ে worst case বের করুন
Memory ব্যবহার মাপুন tracemalloc দিয়ে, আর space complexity-ও estimate করুন
এই estimator দিয়ে Python-এর built-in গুলো পরীক্ষা করুন: list.insert(0, x), dict[k], set.union, str +=
list.append -এর amortised আচরণ দেখান — প্রতিটা append-এর সময় আলাদা করে plot করুন, resize-এর spike গুলো দেখা যাবে
Cache effect যোগ করুন — একই complexity-র দুইটা implementation-এ estimator কি পার্থক্য ধরতে পারে? (পারবে না — আর সেটাই এই লেসনের মূল পাঠ)

বাস্তব সিস্টেমে

Asymptotics যেখানে সিদ্ধান্ত নেয়

Database query planner। PostgreSQL প্রতিটা plan-এর cost estimate করে — sequential scan O(n), index scan O(log n + k), hash join O(n+m), nested loop join O(n·m)। এই estimate-এর উপর ভিত্তি করেই plan বাছা হয়, আর ভুল estimate-ই বেশিরভাগ ধীর query-র কারণ।

API rate limit ও pagination। OFFSET 1000000 কেন ধীর? কারণ database-কে ১০ লক্ষ row পড়ে ফেলে দিতে হয় — O(offset)। Cursor-ভিত্তিক pagination O(log n), তাই বড় dataset-এ সেটাই একমাত্র বিকল্প।

Regex catastrophic backtracking। কিছু regex engine-এ (a+)+b একটা exponential blowup তৈরি করে। ২০১৯-এ Cloudflare-এর বৈশ্বিক outage ঘটেছিল ঠিক এই কারণে — একটা regex CPU ১০০%-এ নিয়ে গিয়েছিল। Level 13-এ আমরা NFA-ভিত্তিক linear-time matching দেখব।

Algorithmic complexity attack। Hash flooding — ইচ্ছাকৃত collision দিয়ে O(1) কে O(n) বানানো, ফলে পুরো table O(n²)। প্রতিকার randomised hash seed। ২০১১-এ বহু web framework আক্রান্ত হয়েছিল।

Compiler-এর optimization pass ordering। কিছু analysis O(n²) বা তার বেশি, তাই বড় function-এ compiler নিজেই optimization বন্ধ করে দেয়। GCC-র --param দিয়ে সেই সীমা নিয়ন্ত্রণ করা যায়।

Kubernetes scheduler। n টা pod, m টা node — naive scoring O(n·m)। বড় cluster-এ (৫০০০ node) সেটা অসহনীয়, তাই scheduler node-এর একটা নমুনা দেখে (default ৫০% বা ন্যূনতম ১০০) — সঠিকতার বিনিময়ে গতি।

Git-এর packfile ও delta compression। Naive delta খোঁজা O(n²) — প্রতিটা object-এর সাথে প্রতিটা। Git একটা sliding window (default ১০) ব্যবহার করে, তাই O(n·w)।

React-এর reconciliation। দুইটা tree-র সাধারণ diff O(n³)। React heuristic দিয়ে সেটা O(n)-এ নামায় — ধরে নেয় ভিন্ন type-এর node-এর subtree সম্পূর্ণ ভিন্ন, আর key দিয়ে list element মেলায়। এজন্যই key prop এত গুরুত্বপূর্ণ।

যে ভুলগুলো সবাই করে

“`O(1)` সবসময় `O(n)`-এর চেয়ে দ্রুত।”

Asymptotic notation n → ∞-এর কথা বলে। আপনার n হয়তো ১০।

O(1) মানে “ধ্রুবক”, কিন্তু সেই ধ্রুবকটা বিশাল হতে পারে:

# O(1) কিন্তু ধীর
def lookup(key):
    conn = connect_to_database()     # ~50 ms
    return conn.get(key)

# O(n) কিন্তু দ্রুত n ছোট হলে
def lookup(key, items):              # items-এ ১০টা element
    for k, v in items:
        if k == key: return v

দ্বিতীয়টা মাইক্রোসেকেন্ডে শেষ।

এই কারণেই ছোট collection-এ linear scan প্রায়ই hash table-কে হারায় — hash গণনার খরচ আর pointer indirection-ই বেশি।

Rust-এর HashMap আর Java-র HashMap উভয়েই ছোট আকারে একটা সরল array ব্যবহার করে, আর একটা threshold পার হলে প্রকৃত hash structure-এ যায়।

নিয়ম: asymptotic দিয়ে scaling নিয়ে যুক্তি করুন, absolute speed নিয়ে নয়। Absolute speed measure করতে হয়।

“Big-O বলে দেয় program কত দ্রুত চলবে।”

Big-O কোনো সময় বলে না। এটা বলে সময় কীভাবে বাড়ে।

O(n) মানে “input দ্বিগুণে সময় দ্বিগুণ” — কিন্তু সেটা ১ মাইক্রোসেকেন্ড থেকে ২, নাকি ১ ঘণ্টা থেকে ২, সে বিষয়ে কিছুই বলে না।

যা যা Big-O-তে অদৃশ্য:

উপাদান	প্রভাব
ধ্রুবক গুণক	১০০ গুণ পর্যন্ত
Cache locality	১০–৫০ গুণ
Branch prediction	২–১০ গুণ
SIMD	৪–১৬ গুণ
Memory allocation	পরিবর্তনশীল
Constant factor of the language	Python বনাম C: ~৫০ গুণ

একটা O(n²) C program একটা O(n log n) Python program-কে n = 10⁵ পর্যন্তও হারাতে পারে।

Big-O একটা scaling model, একটা performance model নয়।

“`O` মানে worst case।”

O আর worst case দুইটা আলাদা অক্ষ, আর এটাই সবচেয়ে সাধারণ বিভ্রান্তি।

Best/average/worst — কোন input বিবেচনা করছেন
O/Ω/Θ — সেই input-এর জন্য কোন সীমা দিচ্ছেন

দুইটা স্বাধীনভাবে মেলানো যায়:

"Quicksort-এর average case Θ(n log n)"       বৈধ
"Quicksort-এর worst case Ω(n²)"              বৈধ
"Insertion sort-এর best case Θ(n)"           বৈধ

শেষটা লক্ষ্য করুন — insertion sort ইতিমধ্যে sorted array-তে Θ(n), কারণ ভেতরের loop সাথে সাথে থামে। এটাই Timsort-এর মূল অন্তর্দৃষ্টি: বাস্তব ডেটায় প্রায়ই sorted run থাকে, তাই সেগুলো খুঁজে বের করে merge করা।

মানুষ যখন বলে “O(n²)”, প্রসঙ্গ থেকে সাধারণত worst case বোঝা যায় — কিন্তু সেটা প্রচলন, সংজ্ঞা নয়।

“Asymptotically ভালো algorithm সবসময় বাছা উচিত।”

প্রায়ই ভুল সিদ্ধান্ত।

তিনটা কারণ:

১. আপনার n ছোট। Crossover point-এর নিচে থাকলে সরল algorithm-ই দ্রুত। সব বাস্তব sort ছোট subarray-তে insertion sort ব্যবহার করে।

২. ধ্রুবক অসহনীয়। Galactic algorithm — asymptotically ভালো কিন্তু কখনো ব্যবহারযোগ্য নয়।

৩. জটিলতার নিজস্ব খরচ আছে। একটা O(n log n) algorithm যদি ৫০০ লাইন হয় আর O(n²)-টা ১০ লাইন, তাহলে প্রথমটায় bug-এর ঝুঁকি, রক্ষণাবেক্ষণের খরচ, আর নতুন ডেভেলপারের বোঝার সময় — সবই বেশি।

সঠিক পদ্ধতি:

সরলতম correct জিনিস লিখুন
আপনার বাস্তব n আর বাস্তব input দিয়ে measure করুন
ধীর হলে profile করুন — bottleneck প্রায়ই অপ্রত্যাশিত জায়গায়
তখন optimize করুন, আর আবার measure করুন

Knuth-এর বাক্যটা এখানে (আর সম্পূর্ণ উদ্ধৃতিটা গুরুত্বপূর্ণ): “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil. Yet we should not pass up our opportunities in that critical 3%.”

শেষ বাক্যটাই সবাই বাদ দেয় — সেই ৩% খুঁজে বের করাই আসল কাজ।

বুঝেছেন কি না দেখুন

n = O(n²) কি সত্য? সত্য হলে, এটা বলা কেন খারাপ?

যুক্তি

সত্য।

সংজ্ঞা অনুযায়ী f(n) = O(g(n)) যদি ∃c, n₀ : ∀n ≥ n₀, f(n) ≤ c·g(n)।

c = 1, n₀ = 1 নিন: ∀n ≥ 1, n ≤ n² — সত্য।

কেন এটা বলা খারাপ: O একটা উপরের সীমা, আর একটা ঢিলা সীমা প্রায় কোনো তথ্য দেয় না।

“আমার বয়স ১০০০ বছরের কম” — সত্য, কিন্তু অকেজো।

এগুলোও সবই সত্য:

n = O(n²) = O(n³) = O(2ⁿ) = O(n!)

যা বলা উচিত: n = Θ(n) — আঁটসাঁট সীমা, দুই দিক থেকেই বাঁধা।

কখন ঢিলা O বৈধ:

কখনো আপনি আঁটসাঁট সীমা জানেন না, বা প্রমাণ করতে পারেননি। তখন O দিয়ে যা জানেন তা বলাই সৎ।

উদাহরণ: matrix multiplication O(n^2.37) — কিন্তু কেউ জানে না সত্যিকারের exponent কত। Lower bound শুধু Ω(n²) (output-ই তো n² টা সংখ্যা)। মাঝের ফাঁকটা একটা খোলা গবেষণা প্রশ্ন।

তাই সেখানে O লেখাটা ঢিলেমি নয় — জ্ঞানের সীমা।

Interview-এ সতর্কতা: কেউ যদি জিজ্ঞেস করে “এই algorithm-এর complexity কত?” আর আপনি O(n²) বলেন যখন এটা আসলে Θ(n log n), তাহলে উত্তরটা technically সত্য কিন্তু আপনি জানেন না বলেই মনে হবে।

Master Theorem দিয়ে সমাধান করুন: (ক) T(n) = 4T(n/2) + n (খ) T(n) = 2T(n/2) + n² (গ) T(n) = 3T(n/3) + n

প্রয়োগ

প্রতিটায় n^(log_b a) আর f(n) তুলনা করি।

(ক) T(n) = 4T(n/2) + n

a = 4, b = 2 → log₂ 4 = 2 → n²

f(n) = n = O(n^{2−1}), অর্থাৎ ε = 1-এ ক্ষেত্র ১।

$T(n) = \Theta(n^2)$

পাতায় কাজ প্রাধান্য পায়। (এটাই naive matrix multiplication-এর recurrence-এর সরলীকৃত রূপ।)

(খ) T(n) = 2T(n/2) + n²

a = 2, b = 2 → log₂ 2 = 1 → n

f(n) = n² = Ω(n^{1+1}), অর্থাৎ ক্ষেত্র ৩।

Regularity যাচাই: a·f(n/b) ≤ c·f(n) কোনো c < 1-এর জন্য? 2·(n/2)² = n²/2 ≤ 0.5·n² — হ্যাঁ, c = 0.5।

$T(n) = \Theta(n^2)$

মূলের কাজ প্রাধান্য পায়।

(গ) T(n) = 3T(n/3) + n

a = 3, b = 3 → log₃ 3 = 1 → n

f(n) = n = Θ(n) — ক্ষেত্র ২।

$T(n) = \Theta(n \log n)$

সব স্তরে সমান কাজ, আর log₃ n টা স্তর।

একটা সুন্দর পর্যবেক্ষণ: (গ) আর merge sort (2T(n/2)+n) দুটোই Θ(n log n) — যদিও একটা তিন ভাগে, একটা দুই ভাগে ভাগ করে।

কারণ base পরিবর্তনে শুধু একটা ধ্রুবক আসে: log₃ n = log₂ n / log₂ 3। তাই asymptotically একই।

এজন্যই আমরা Θ(n log n) লিখি, Θ(n log₂ n) নয় — logarithm-এর base একটা ধ্রুবক গুণক মাত্র।

Dynamic array যদি প্রতিবার 2×-এর বদলে 1.5× বাড়ে, amortised খরচ কি বদলায়? আর +100 করে বাড়লে?

যুক্তি

1.5× — এখনো Θ(1) amortised।

Resize গুলোতে মোট copy খরচ একটা geometric series:

$n + \frac{n}{1.5} + \frac{n}{1.5^2} + \cdots = n \cdot \frac{1}{1 - 1/1.5} = 3n$

2×-এ ছিল 2n, এখানে 3n — ধ্রুবক গুণক বেড়েছে, class বদলায়নি।

সাধারণভাবে growth factor k > 1 হলে:

$\text{মোট copy} = \frac{n}{1 - 1/k} = \frac{kn}{k-1}$

`k`	মোট copy	সর্বোচ্চ অপচয়ী জায়গা
1.25	`5n`	20%
1.5	`3n`	33%
2	`2n`	50%
4	`1.33n`	75%

Trade-off: k বড় হলে কম copy কিন্তু বেশি memory অপচয়।

আর একটা সূক্ষ্ম সুবিধা k < 2-তে: মুক্ত হওয়া পুরনো block গুলো মিলে পরের allocation-এর জন্য যথেষ্ট হতে পারে, তাই allocator সেগুলো পুনর্ব্যবহার করতে পারে। k = 2-এ কখনো পারে না (1+2+4+...+2^(i-1) < 2^i)। এই কারণেই Facebook-এর folly::fbvector 1.5× ব্যবহার করে।

+100 — সম্পূর্ণ ভেঙে পড়ে।

Resize ঘটে n = 100, 200, 300, …, তাই n/100 বার। প্রতিবার copy খরচ বর্তমান আকার:

$100 + 200 + \cdots + n = \frac{100 + n}{2} \cdot \frac{n}{100} = \Theta(n^2)$

Amortised খরচ Θ(n²)/n = Θ(n) — প্রতিটা append গড়ে রৈখিক।

n = 10⁶ হলে মোট 5×10⁹ copy operation — কয়েক সেকেন্ড, যেখানে geometric growth-এ কয়েক মিলিসেকেন্ড।

মূল নীতি: amortised Θ(1) পেতে বৃদ্ধি গুণিতক হতে হবে, যোগিক নয়। যেকোনো k > 1 কাজ করে; যেকোনো ধ্রুবক যোগ ব্যর্থ।

একই নীতি অন্যত্র:

Hash table rehashing — load factor threshold-এ দ্বিগুণ
Exponential backoff — retry delay গুণিতকভাবে বাড়ে
TCP slow start — congestion window গুণিতকভাবে বাড়ে

একটা সিস্টেমে আপনার কাছে দুইটা বিকল্প: O(n log n) কিন্তু ৫০০ লাইনের জটিল algorithm, নাকি O(n²) কিন্তু ১৫ লাইনের সরল algorithm। কীভাবে সিদ্ধান্ত নেবেন?

ডিজাইন

প্রশ্নটা asymptotic নয় — প্রকৌশলগত। ছয়টা প্রশ্ন করুন।

১. আপনার n-এর বাস্তব পরিসর কত?

এটাই সবচেয়ে গুরুত্বপূর্ণ প্রশ্ন, আর প্রায়ই কেউ জিজ্ঞেস করে না।

`n`	`n²`	`n log n`	সিদ্ধান্ত
100	10⁴	664	সরলটা — পার্থক্য অদৃশ্য
10,000	10⁸	1.3×10⁵	নির্ভর করে
10⁶	10¹²	2×10⁷	জটিলটা লাগবেই

২. n কি বাড়বে?

আজ ১০০, কিন্তু তিন বছরে ১০ লক্ষ হলে? তখন rewrite-এর খরচ এখনকার সাশ্রয়ের চেয়ে বেশি হতে পারে।

উল্টোদিকে, যদি n স্থিরভাবে ছোট থাকে (যেমন একটা config ফাইলের entry সংখ্যা), তাহলে কখনোই লাগবে না।

৩. এটা কি hot path-এ?

দিনে একবার চলে, নাকি প্রতিটা request-এ? Startup-এ ৫০ ms কেউ খেয়াল করবে না; প্রতি request-এ ৫০ ms বিপর্যয়।

৪. Correctness-এর ঝুঁকি কত?

৫০০ লাইনে bug লুকানোর জায়গা অনেক বেশি। যদি এটা billing বা security-সংক্রান্ত হয়, সরলতার মূল্য অনেক বেশি।

৫. রক্ষণাবেক্ষণের খরচ?

ছয় মাস পরে কে এটা পড়বে? একটা জটিল algorithm যদি ভালোভাবে নথিভুক্ত না থাকে, সেটা একটা দায়।

৬. তৃতীয় বিকল্প আছে কি?

প্রায়ই সেরা উত্তর: library ব্যবহার করুন। কেউ ইতিমধ্যে সেই ৫০০ লাইন লিখেছে, test করেছে, আর optimize করেছে।

আমার সুপারিশ — পর্যায়ক্রমে:

def process(items):
    if len(items) \<= THRESHOLD:
        return simple_quadratic(items)     # ১৫ লাইন, পরিষ্কার
    return complex_nlogn(items)            # শুধু যখন দরকার

এটাই বাস্তব library-গুলো করে (introsort, Timsort)।

কিন্তু শুরু করুন সরলটা দিয়ে:

সরল version লিখুন, ভালো test সহ
বাস্তব ডেটা দিয়ে measure করুন
যদি সত্যিই bottleneck হয়, তখন জটিলটা যোগ করুন
দুইটা একই উত্তর দেয় কি না property-test করুন

শেষ ধাপটা গুরুত্বপূর্ণ — সরল version টাই জটিলটার reference implementation হয়ে যায়।

যা করবেন না: n না জেনে জটিলটা বেছে নেওয়া। এটাই premature optimization, আর এতে আপনি জটিলতার দাম দিলেন কিন্তু হয়তো কোনো লাভই পেলেন না।

Quicksort-এর worst case-এর Ω কত? আর best case-এর O কত? প্রশ্নদুটো অর্থবহ কি না ব্যাখ্যা করুন।

যুক্তি

দুটোই সম্পূর্ণ অর্থবহ — আর এই প্রশ্নটাই দুইটা অক্ষের স্বাধীনতা পরীক্ষা করে।

Worst case-এর Ω:

Worst case ঘটে যখন pivot সবসময় সবচেয়ে ছোট বা বড় element (যেমন ইতিমধ্যে sorted array-তে first-element pivot নিলে)।

তখন recurrence: $T(n) = T(n-1) + \Theta(n)$

সমাধান: $T(n) = n + (n-1) + \cdots + 1 = \frac{n(n+1)}{2} = \Theta(n^2)$

Θ(n²) মানে O(n²) এবং Ω(n²) দুটোই।

উত্তর: worst case-এর Ω হলো Ω(n²)।

Best case-এর O:

Best case ঘটে যখন pivot সবসময় ঠিক মাঝখানে: $T(n) = 2T(n/2) + \Theta(n) = \Theta(n \log n)$

উত্তর: best case-এর O হলো O(n log n)।

কেন প্রশ্নদুটো অর্থবহ:

দুইটা স্বাধীন সিদ্ধান্ত নিতে হয়:

কোন input? — best, average, বা worst
কোন সীমা? — O (উপরে), Ω (নিচে), Θ (দুই দিকে)

প্রথমটা একটা নির্দিষ্ট function বেছে দেয় (যেমন T_worst(n)), দ্বিতীয়টা সেই function-কে বর্ণনা করে।

সম্পূর্ণ ছবিটা:

	Best	Average	Worst
Quicksort	`Θ(n log n)`	`Θ(n log n)`	`Θ(n²)`
Merge sort	`Θ(n log n)`	`Θ(n log n)`	`Θ(n log n)`
Insertion sort	`Θ(n)`	`Θ(n²)`	`Θ(n²)`
Timsort	`Θ(n)`	`Θ(n log n)`	`Θ(n log n)`

ব্যবহারিক তাৎপর্য — কেন তবু quicksort ব্যবহার হয়:

Merge sort-এর worst case ভালো, তবু quicksort বেশি জনপ্রিয়:

Quicksort in-place (O(log n) stack), merge sort O(n) extra memory
Quicksort-এর ধ্রুবক ছোট, আর cache locality ভালো (partition sequential)
Random pivot দিয়ে worst case কার্যত অসম্ভব করা যায় (probability-র লেসনে আমরা expected O(n log n) প্রমাণ করেছি)

Introsort সেরা সমাধান: quicksort দিয়ে শুরু, recursion depth 2 log n ছাড়ালে heapsort-এ সরে যায়। তখন worst case গ্যারান্টি O(n log n), আর সাধারণ ক্ষেত্রে quicksort-এর গতি। C++-এর std::sort এটাই।

Timsort-এর best case Θ(n) লক্ষ্য করুন — ইতিমধ্যে sorted ডেটায় একবার scan করেই বুঝে যায়। বাস্তব ডেটায় প্রায়ই sorted run থাকে, তাই Python আর Java-র default।

এরপর কী

Level 0 শেষ

পিছনে তাকান। ষোলোটা লেসনে আমরা একটা সম্পূর্ণ চিন্তার যন্ত্র তৈরি করেছি:

Logic দিয়ে দাবি প্রকাশ করতে শিখলাম। Proof দিয়ে সেগুলো প্রতিষ্ঠা করতে শিখলাম — আর induction দিয়ে অসীমকে ধরতে। Set, relation, function, graph দিয়ে কাঠামো বর্ণনা করতে শিখলাম। Combinatorics ও probability দিয়ে গুনতে আর অনিশ্চয়তা সামলাতে। Boolean algebra দিয়ে logic-কে circuit-এর দোরগোড়ায় নিয়ে গেলাম, number theory দিয়ে বিচ্ছিন্ন জগতের হিসাব, linear algebra দিয়ে রূপান্তরের ভাষা, আর asymptotics দিয়ে “ভালো” শব্দটার একটা সংজ্ঞা।

এগুলো আলাদা বিষয় ছিল না। প্রতিটা লেসন আগেরগুলোর উপর দাঁড়িয়েছে — De Morgan logic থেকে set-এ, set থেকে quantifier-এ; induction থেকে recursion-এ, recursion থেকে recurrence-এ; function-এর injectivity থেকে hash collision-এ, সেখান থেকে determinant-এ।

এতক্ষণ যা শিখলাম সেটা ভাষা। Level 1 থেকে সবকিছু ভৌত হয়ে যাবে।

পরের module — Computer Representation — শুরু হবে একটামাত্র প্রশ্ন দিয়ে:

একটা bit pattern 01000001 — এটা কি সংখ্যা ৬৫? অক্ষর A? একটা float-এর টুকরো? একটা machine instruction?

উত্তর: pattern নিজে কিছু বলে না। Interpretation বলে।

সেখানে আমরা দেখব two’s complement আসলে mod 2ⁿ arithmetic (আজকের number theory), IEEE 754-এর প্রতিটা bit কী করে, UTF-8 কেন injective হতে বাধ্য (functions-এর লেসন), আর কেন 0.1 + 0.2 ≠ 0.3 — যে প্রশ্নটা দিয়ে এই পুরো module শুরু হয়েছিল।

Asymptotic Notation — বৃদ্ধির হারের ভাষা

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

আগে এটা বুঝি

মূল ধারণা

আনুষ্ঠানিক সংজ্ঞা

Big O — উপরের সীমা

Big Omega — নিচের সীমা

Big Theta — আঁটসাঁট সীমা

ছোট o এবং ω — কঠোর সীমা

বৃদ্ধির হারের সোপান

সরলীকরণের নিয়ম

Loop বিশ্লেষণ

Recurrence আর Master Theorem

Amortised analysis

দুইটা আলাদা অক্ষ — এটা গুলিয়ে ফেলবেন না

ভেতরে কী ঘটছে

যেখানে asymptotic analysis মিথ্যা বলে

১. ধ্রুবক বাস্তবে গুরুত্বপূর্ণ

২. Cache locality — সবচেয়ে বড় মিথ্যা

৩. Galactic algorithm

৪. Memory hierarchy asymptotics বদলে দেয়

৫. Amortised বনাম tail latency

উদাহরণ

একটা সম্পূর্ণ বিশ্লেষণ

Space complexity — যা প্রায়ই ভুলে যাওয়া হয়

নিজে চালিয়ে দেখুন

Timing থেকে exponent উদ্ধার করুন

যেখানে Big-O মিথ্যা বলে — cache locality

নিজে বানান

Empirical Complexity Estimator

বাস্তব সিস্টেমে

Asymptotics যেখানে সিদ্ধান্ত নেয়

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী

Level 0 শেষ

আরও পড়ুন

এই লেসন শেষে আপনি পারবেন

আগে যা বোঝা থাকা দরকার

◔আগে এটা বুঝিWhy this matters

◆মূল ধারণাCore concept

আনুষ্ঠানিক সংজ্ঞা

Big O — উপরের সীমা

Big Omega — নিচের সীমা

Big Theta — আঁটসাঁট সীমা

ছোট o এবং ω — কঠোর সীমা

বৃদ্ধির হারের সোপান

সরলীকরণের নিয়ম

Loop বিশ্লেষণ

Recurrence আর Master Theorem

Amortised analysis

দুইটা আলাদা অক্ষ — এটা গুলিয়ে ফেলবেন না

⚙ভেতরে কী ঘটছেUnder the hood

যেখানে asymptotic analysis মিথ্যা বলে

১. ধ্রুবক বাস্তবে গুরুত্বপূর্ণ

২. Cache locality — সবচেয়ে বড় মিথ্যা

৩. Galactic algorithm

৪. Memory hierarchy asymptotics বদলে দেয়

৫. Amortised বনাম tail latency

▶উদাহরণExample

একটা সম্পূর্ণ বিশ্লেষণ

Space complexity — যা প্রায়ই ভুলে যাওয়া হয়

⌘নিজে চালিয়ে দেখুনExperiment

Timing থেকে exponent উদ্ধার করুন

যেখানে Big-O মিথ্যা বলে — cache locality

⚒নিজে বানানBuild it yourself

Empirical Complexity Estimator

◉বাস্তব সিস্টেমেReal-world usage

Asymptotics যেখানে সিদ্ধান্ত নেয়

⚠যে ভুলগুলো সবাই করেMisconceptions

?বুঝেছেন কি না দেখুনCheck understanding

→এরপর কীNext step

Level 0 শেষ

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

নিজে চালিয়ে দেখুন

নিজে বানান

বাস্তব সিস্টেমে

যে ভুলগুলো সবাই করে

বুঝেছেন কি না দেখুন

এরপর কী