Asymptotic Analysis — O, Θ, Ω: growth-এর ভাষা

আগে এটা বুঝি

এই module-এর driving question-টা প্রথম পড়লে প্রায় childish লাগে: দুইটা correct solution-এর মধ্যে কোনটা ভালো, আর “ভালো” মানে ঠিক কী? Correct হওয়া তো ব্যাপারই শেষ — ভুল উত্তর দেওয়া program নিয়ে তুলনার প্রশ্নই ওঠে না। কিন্তু ঠিক এখানেই আসল কাজ শুরু। একই problem-এর দুইটা সঠিক সমাধান থাকল — একটা ৩ সেকেন্ডে শেষ, আরেকটা ৩০ মিনিটে। প্রথমটা “ভালো”? এত সহজ না। কোন মেশিনে ৩ সেকেন্ড? কোন input-এ? input দশগুণ বড় হলে কী হবে?

সেই definition-এর ভাষাটাই আজকের বিষয়: Asymptotic Notation — O, Θ, Ω, আর তাদের ছোট ভাইবোন o ও ω। এটা এমন এক ভাষা যেখানে “এই অ্যালগরিদমটা input বাড়লে কীভাবে খরচ বাড়ে” কথাটা বলা যায় কোনো নির্দিষ্ট CPU, clock speed, বা programming language-এর প্রসঙ্গ ছাড়াই।

আজকের প্রশ্ন তিনটা: (১) মিলিসেকেন্ড মাপার বদলে growth গুনব কেন? (২) O, Θ, Ω ঠিক কোন দাবি করে, আর কোনটা করে না? (৩) এই তত্ত্ব বাস্তব মেশিনে মেপে কীভাবে verify করব — আর কোথায় theory আর reality-র ফারাক চোখে পড়বে?

মূল ধারণা

মিলিসেকেন্ড কেন মিথ্যা বলে

ধরুন আপনি দুইটা sorting function benchmark করলেন নিজের laptop-এ:

	input n = ১০,০০০	input n = ১,০০,০০০
sortA	12 ms	140 ms
sortB	9 ms	2100 ms

n = ১০,০০০-তে sortB জিতেছে। n = এক লাখে ১৫ গুণ হেরে গেছে। কোনটা ভালো অ্যালগরিদম? প্রশ্নটাই ভুল — সঠিক প্রশ্ন: n বাড়ার সঙ্গে সঙ্গে কার খরচ কত দ্রুত বাড়ে? sortA-র খরচ প্রায় রৈখিকভাবে বাড়ছে (১০× input → প্রায় ১২× সময়), sortB-র খরচ প্রায় শতগুণ (১০× input → ২৩৩× সময়)। sortB-কে অনুকূল ছোট input দিলে সে আরও এগিয়ে যেতে পারে; কিন্তু n যত বড় হবে, ফারাক তত অপ্রতিরোধ্য হবে।

মিলিসেকেন্ডের সংখ্যাটা আসলে তিনটা আলাদা জিনিসের mixture — অ্যালগরিদমের কাজের পরিমাণ, মেশিনের গতি, আর compiler/interpreter-র দক্ষতা। প্রথমটা আমাদের দরকার, শেষ দুটো বিভ্রান্তি। Asymptotic analysis শেষ দুটোকে বাদ দিয়ে প্রথমটা আলাদা করে দেখার চুক্তি: মেশিন বদলালে সব runtime প্রায় একই ফ্যাক্টরে scale করে, তাই অনুপাত আর আকৃতি রেখে দিয়ে absolute number ফেলে দেওয়া।

পাঁচটা notation — আনুষ্ঠানিক সংজ্ঞা

f আর g দুইটা function, n → ∞-এর দিকে তাকিয়ে আছি। মনে রাখুন — এরা runtime-এর সরাসরি মাপ না, runtime-এর কোনো model (সাধারণত basic operation-এর সংখ্যা)।

Notation	পাঠোদ্ধার	Definition (constants)	Limit characterization
f = O(g)	g হলো upper bound	ধনাত্মক constant c ও n₀ আছে যেন n ≥ n₀-তে f(n) ≤ c·g(n)	lim sup f/g সসীম
f = Ω(g)	g হলো lower bound	ধনাত্মক constant c ও n₀ আছে যেন n ≥ n₀-তে f(n) ≥ c·g(n)	lim inf f/g positive
f = Θ(g)	g হলো tight bound	O এবং Ω দুই-ই	lim f/g একটা positive সসীম সংখ্যা
f = o(g)	strictly ছোট	প্রতিটা ধনাত্মক c-এর জন্যই যথেষ্ট বড় n-এ f(n) ≤ c·g(n)	lim f/g = 0
f = ω(g)	strictly বড়	প্রতিটা ধনাত্মক c-এর জন্যই যথেষ্ট বড় n-এ f(n) ≥ c·g(n)	lim f/g = ∞

তিনটা সূক্ষ্মতা, যেগুলোতে বেশিরভাগ ভুল হয়:

এক, O একটা উপরের সীমার দাবি, equality-র না। linear_search = O(n²) সত্য বাক্য! কারণ যে খরচ n-এ বাড়ে সেটা নিশ্চিতভাবে n²-এর সীমার নিচেও থাকে। তাই কথ্য ভাষায় “big-O” বললে আমরা প্রায়ই Θ বুঝি — সবচেয়ে tight দাবি। পরীক্ষায়, code review-তে, documentation-এ পার্থক্যটা মাথায় রাখুন।

দুই, constants আর ছোট n ইচ্ছামতো বাদ। n² অপারেশনের কাজ আর 1000000·n অপারেশনের কাজ দুই-ই O(n²) আর O(n) যথাক্রমে — কিন্তু বাস্তবে দ্বিতীয়টা n এক কোটি পর্যন্ত প্রথমটাকে হারাবে। এটা feature, bug না: asymptotics বলে দেয় কোন সীমার ওপারে কে জিতবে, কত n-এ জিতবে বলে না।

তিন, base of logarithm পার্থক্য করে না — log₂n = ln n / ln 2, মানে constant factor, আর Θ সেই factor খেয়ে ফেলে। তাই O(log n) বললে base লেখার দরকার নেই।

Θ-কেন Knuth এত গুরুত্ব দিয়েছিলেন

1976-এ Knuth লিখলেন “Big Omicron and big Omega and big Theta” — যুক্তি ছিল: O শুধু উপর থেকে চাপ দেয়, তাই “এই অ্যালগরিদমের complexity কত” প্রশ্নের উত্তর হিসেবে O অসম্পূর্ণ। Tight statement দরকার: merge sort-এর খরচ হুবহু n log n-এর order-এ — না তার সাধারণত কম, না সাধারণত বেশি। সেই দাবির নাম Θ(n log n)। আজকের দিনে প্রায় প্রতিটা serious analysis Θ দিয়েই শেষ হয়; O থাকে যখন tight bound প্রমাণ করা কঠিন (যেমন কিছু graph algorithm-এর সর্বোত্তম নিচের সীমা)।

Best, average, worst — এক অ্যালগরিদম, তিনটা গল্প

একটা function-এর growth বলা মানে আসলে বলা: কোন input-এর উপর? Insertion sort নিন। n টা element sort করতে হবে:

Worst case (উল্টো করা list): প্রতিটা element প্রায় পুরো prefix traverse করে — তুলনা মোটামুটি n(n−1)/2 ≈ n²/2 → Θ(n²)
Best case (already sorted): প্রতিটা element একটাই তুলনা করে — Θ(n)
Average case (random permutation): প্রত্যাশিত তুলনা ≈ n²/4 → এখনও Θ(n²), কিন্তু constant অর্ধেক

লক্ষ্য করুন average case-এর দাবিটা অন্যরকম — এটা একটা probability distribution ধরে নেয় (সব input সমসম্ভাব্য)। Worst case-এর দাবি deterministic: কোনো input-ই আমাকে এর চেয়ে খারাপ ধরতে পারবে না। Real-time system, adversarial environment (network server!), বা security-critical কোডে worst case-ই রাজা; বিশ্লেষণী tooling-এ গড় case বেশি কাজের। দুটোর মধ্যে কোনটা “সঠিক প্রশ্ন” — সেটা application-এর ব্যাপার, mathematics-এর না।

Growth-এর সিঁড়ি — concrete সংখ্যায়

Common classes গুলো পাশাপাশি রাখি। ধরুন মেশিনে সেকেন্ডে ১০⁸ basic operation চলে (modern CPU-তে compiled code-এর জন্য realistic):

Class	n = 10	n = 1,000	n = 10⁶
O(1)	instant	instant	instant
O(log n)	~3 ops	~10 ops	~20 ops
O(n)	10 ops	10³ ops	10⁶ ops ≈ 0.01 s
O(n log n)	~33 ops	~10⁴ ops	~2×10⁷ ≈ 0.2 s
O(n²)	100 ops	10⁶ ≈ 0.01 s	10¹² ≈ 2.8 ঘণ্টা

Amortized bound-এর আভাস — পরের লেসনের প্রতিশ্রুতি

Python-এর list.append documentation বলে append-এর খরচ “O(1)”। কিন্তু মাঝে মাঝে একটা append পুরো array copy করে — worst case প্রতি-অপারেশনে তাহলে O(n)! দুই বাক্যই সত্য, কারণ ওই O(1) আসলে amortized O(1): দুষ্ট একটা দামি append-কে তার আগের সস্তাদের সঞ্চয় দিয়ে শোধ করা যায়। পরের লেসনে এই হিসাবটা পুরোপুরি খুলব — aggregate, accounting, potential তিন পদ্ধতিতে। আপাতত মনে রাখুন: asymptotic family-তে bound-এর ধরনও (gross/worst/amortized/expected) ঠিক করা bound-এর মানের অংশ।

ভেতরে কী ঘটছে

Theory কী লুকায় — আর কেন তবুও কাজের

Θ notation ইচ্ছাকৃতভাবে অনেক কিছু ফেলে দেয়। কী ফেলে দিচ্ছি, জেনে ফেলাটাই professional ব্যবহারের প্রথম শর্ত:

Constant factor — C-তে লেখা O(n log n) আর Python-এ লেখা O(n), বাস্তবে প্রায়ই Python-টাই জেতে, ৫০–১০০× interpreter tax সত্ত্বেও না, বরং ছোট-মাঝারি n-এ। Factor 100 মানে crossover point n ≈ 100·log n — মানে লক্ষাধিক element পর্যন্ত “তাত্ত্বিকভাবে খারাপ” O(n log n) C-কোড আসলে এগিয়ে থাকে।
Memory behavior — দুইটা Θ(n) traversal, একটা sequential scan, আরেকটা random hop — cache-এর কাছাকাছি একটা, দূরে আরেকটা। এই ফারাক প্রায়ই ১০× — কিন্তু Θ notation দুটোকেই Θ(n) বলে। পরের লেসনগুলোতে এটাই আমাদের প্রধান বিষয় হবে। তাহলে asymptotics কেন তবুও প্রথম সরঞ্জাম? কারণ এটা scale-এর আইন: constant factor দিয়ে hardware কিনে নেওয়া যায়, growth curve কিনে নেওয়া যায় না। n ১০০ গুণ হলে O(n) কাজ ১০০ গুণ — বড় মেশিন দিয়ে সামলানো যায়; O(n²) কাজ ১০,০০০ গুণ — মেশিন দিয়ে না, অ্যালগরিদম বদলেই সমাধান। Professional judgment মানে দুই layer একসাথে পড়া: প্রথমে asymptotic class, তারপর class-এর ভেতরের constant আর memory story।

Doubling ratio — measurement থেকে class শনাক্ত

Definition থেকেই একটা চমৎকার empirical কৌশল ওঠে। T(n) = c·n² হলে:

$\frac{T(2n)}{T(n)} = \frac{c \cdot (2n)^2}{c \cdot n^2} = 4$

Constant c মুছে গেল! অর্থাৎ input দ্বিগুণ করলে সময় কতগুণ হয় — এই একটা সংখ্যাই class-এর fingerprint, মেশিনের গতি নিরপেক্ষভাবে:

Growth	T(2n)/T(n) প্রত্যাশিত	মানে
O(1)	≈ 1	সময় সমতল
O(log n)	1 থেকে সামান্য বেশি (যেমন 11/10)	খুব ধীরে বাড়ে
O(n)	≈ 2	সরলরৈখিক
O(n log n)	2-এর সামান্য ওপরে, ধীরে 2-এর দিকে	প্রায়-রৈখিক
O(n²)	≈ 4	দ্বিঘাত
O(n³)	≈ 8	ত্রিঘাত
O(2ⁿ)	≈ 2 × আগের অনুপাত	প্রতি ধাপে অনুপাতই দ্বিগুণ

সাবধানে খেয়াল করুন: O(n) আর O(n log n)-এর doubling ratio কাছাকাছি — দুটোই 2-এর আশেপাশে। এই ambiguity মেটাতে দরকার fitting: মাপা সময়গুলোকে candidate curves (n, n log n, …) দিয়ে fit করে দেখা কোনটা সবচেয়ে ভালো মেলে। আজকের build ঠিক এটাই করবে।

T(n) = Θ(n²) দাবিটার যাত্রা — definition থেকে measurement

Mathematical claimএমন c₁, c₂, n₀ আছে যেন n ≥ n₀-তে c₁·n² ≤ T(n) ≤ c₂·n² — দুই দিক থেকে বেঁধে
Operation modelbasic operation বেছে নেওয়া (তুলনা, assignment) — machine-independent counting
Input modelworst case বলছি: সব n-length input-এর মধ্যে সর্বোচ্চ খরচ — distribution লাগে না
Empirical testdoubling ratio ≈ 4 মাপা গেল — মেশিন constant c মুছে যায়, আকৃতিটাই থাকে

উদাহরণ

তিনটা function, হাতে-হাতে analysis

কেস ১ — array-র যোগফল:

def total(xs):
    acc = 0
    for v in xs:
        acc += v
    return acc

Loop body প্রতি iteration-এ constant কাজ। Iteration সংখ্যা n। মোট খরচ = a·n + b (a = প্রতি-element খরচ, b = setup)। উপরে থেকে: a·n + b ≤ (a+b)·n যখন n ≥ 1, তাই O(n)। নিচ থেকে: a·n + b ≥ a·n, তাই Ω(n)। দুই-ই মিলে Θ(n) — tight, ঝগড়ার জায়গা নেই।

কেস ২ — duplicate জোড়া গোনা (naive):

def dup_pairs(xs):
    n = len(xs)
    cnt = 0
    for i in range(n):
        for j in range(i + 1, n):
            if xs[i] == xs[j]:
                cnt += 1
    return cnt

ভেতরের loop চলে n−1, n−2, …, 0 বার — মোট তুলনা n(n−1)/2। Upper: n(n−1)/2 ≤ n²/2 → O(n²)। Lower: n(n−1)/2 ≥ (n/2)·(n/2)/2 = n²/8 যখন n ≥ 2 → Ω(n²)। সুতরাং Θ(n²) — আবারও tight। লক্ষ্য করুন lower bound-টা কীভাবে পেলাম: half-point থেকে নিচের দিকের অর্ধেক অংশ ধরে হিসাব — standard trick।

কেস ৩ — sorted array-তে binary search:

প্রতিটা তুলনা search space অর্ধেক করে। k ধাপ পরে space n/2ᵏ। Space 1 হতে হলে k = log₂ n। Best case একটাই তুলনা (middle-এই পাওয়া গেল) — Θ(1)। Worst ও average — Θ(log n)। আর এখানেই best/worst-এর ফারাক সবচেয়ে নাটকীয়: log n আর 1 — দুইটাই ছোট, কিন্তু তাদের অনুপাতও অসীমে যায়।

সবশেষে একটা সৎ প্রশ্ন: কেস ২-এর জন্য hash set দিয়ে Θ(n)-expected solution আছে (পরের কয়েক লেসনে সেটা বানাবেনই)। দুইটা correct solution — Θ(n²) deterministic বনাম Θ(n) expected। কোনটা ভালো? এখন আপনার হাতে ভাষা আছে প্রশ্নটা যথাযথভাবে করার: কোন input model, কোন n-range, কোন constant। এই module-এর পুরো কাজ সেই প্রশ্নগুলোর উত্তর তৈরি করা।

ছবিতে

Growth curve-এর আকৃতি — এক নজরে

খরচ (log scale, শুধু আকৃতির জন্য)

2^n      │                                    ▲
         │                                   ▲▲
n^2      │                          ▲▲   ▲▲
         │                     ▲▲       ▲
n log n  │              ▲▄▄▄▄▄▄
n        │       ▄▄▄▄▄▄
log n    │ ▄▄▄▄▄
O(1)     │▄─────────────────────────────────────▶ n
          ছোট n-এ সবাই প্রায় একই — পার্থক্য ফোটে ডান দিকে

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

EXPERIMENT

Growth Lab — চারটা function, doubling ratio, আর class-fit

Linux/macOS, Python 3.8+· ১৫ মিনিট

# growth_lab.py — doubling experiment দিয়ে growth class চেনা
import time

SIZES = [512, 1024, 2048, 4096]

def f_constant(xs):
    return xs[len(xs) // 2]                 # একটাই access — input যা-ই হোক

def f_log(xs):
    target = -1                             # অনুপস্থিত — worst case
    lo, hi = 0, len(xs) - 1
    while hi >= lo:
        mid = (lo + hi) // 2
        if xs[mid] == target:
            return mid
        if xs[mid] > target:
            hi = mid - 1
        else:
            lo = mid + 1
    return -1

def f_linear(xs):
    cnt = 0
    for v in xs:
        cnt += v % 2                        # প্রতিটা element-এ একবার
    return cnt
def f_quadratic(xs):
    cnt = 0
    n = len(xs)
    for i in range(n):
        xi = xs[i]
        for j in range(i + 1, n):
            if xi == xs[j]:
                cnt += 1
    return cnt

FUNCS = [('constant', f_constant), ('log', f_log),
         ('linear', f_linear), ('quadratic', f_quadratic)]

def bench(fn, n, reps=7):
    xs = list(range(n))                     # sorted — binary search-এর জন্য
    fn(xs)                                  # warm-up
    best = float('inf')
    for _ in range(reps):
        t0 = time.perf_counter()
        fn(xs)
        best = min(best, time.perf_counter() - t0)
    return best

print(f'{"func":>10} ' + " ".join(f'{s:>9}' for s in SIZES) + '   ratios')
for name, fn in FUNCS:
    ts = [bench(fn, n) for n in SIZES]
    ratios = [ts[i+1] / ts[i] for i in range(len(ts) - 1)]
    cells = " ".join(f'{t*1000:9.3f}' for t in ts)
    rs = " ".join(f'{r:5.2f}' for r in ratios)
    print(f'{name:>10} {cells}   [{rs}]')

Typical ফলাফল (absolute সময় machine-ভেদে বদলাবে, ratios প্রায় বদলাবে না):

      func       512      1024      2048      4096   ratios
   constant     0.001     0.001     0.001     0.001   [ 1.00  0.98  1.01]
        log     0.002     0.002     0.003     0.003   [ 1.13  1.08  1.05]
     linear     0.031     0.062     0.126     0.255   [ 2.00  2.03  2.02]
  quadratic    24.1      96.8     387.5    1552.0    [ 4.02  4.00  4.01]

speed না জেনেও প্রতিটা function-এর class বলে দিল। যা প্রমাণিত: growth class একটা measurable, machine-independent বাস্তবতা — theory-র limit definition-এর সঙ্গে আপনার CPU-র stopwatch একই কথা বলছে।

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

Input দ্বিগুণ করলে runtime-এর অনুপাত constant factor আর মেশিনের গতি মুছে growth class-এর fingerprint দেয় — constant ≈ 1, log ≈ 1+, linear ≈ 2, quadratic ≈ 4; theory-র ভবিষ্যদ্বাণী নিজের মেশিনেই verify হয়।

নিজে বানান

BUILD IT

GrowLens — unknown function-এর complexity auto-classifier

Python · ●●○○○

একটা measure(fn, sizes) লিখুন — প্রতিটা n-এ best-of-reps সময় নেয়
Candidate class-এর তালিকা বানান — 1, log2(n), n, n·log2(n), n², n³ — প্রতিটার একটা shape-function সহ
মাপা সময় আর candidate curve দুটোকেই প্রথম point দিয়ে normalise করুন — unit আর constant মুছে যায়
প্রতিটা candidate-এর সর্বোচ্চ relative deviation হিসাব করুন — সবচেয়ে কম deviation-ই verdict
Runner-up error-ও প্রিন্ট করুন — ambiguity দেখতে পারাটা সমান গুরুত্বপূর্ণ

লক্ষ্য: একটা black-box function দিলে হার্নেস নিজেই বলে দেবে তার growth class — ঠিক profiler বা interview panel যেভাবে reverse-engineer করে।

# growlens.py — unknown function-এর growth class স্বয়ংক্রিয় শনাক্তকারী
# চালান: python3 growlens.py
import time, math

CANDIDATES = [
    ('O(1)',       lambda n: 1.0),
    ('O(log n)',   lambda n: math.log2(max(n, 2))),
    ('O(n)',       lambda n: float(n)),
    ('O(n log n)', lambda n: n * math.log2(max(n, 2))),
    ('O(n^2)',     lambda n: float(n * n)),
    ('O(n^3)',     lambda n: float(n) ** 3),
]

def measure(fn, sizes, reps=5):
    out = []
    for n in sizes:
        best = float('inf')
        for _ in range(reps):
            t0 = time.perf_counter()
            fn(n)
            best = min(best, time.perf_counter() - t0)
        out.append(best)
    return out

def classify(times, sizes):
    norm_t = [t / times[0] for t in times]
    scores = []
    for name, shape in CANDIDATES:
        raw = [shape(n) for n in sizes]
        norm_g = [g / raw[0] for g in raw]
        err = max(abs(a - b) / max(b, 1e-9) for a, b in zip(norm_t, norm_g))
        scores.append((err, name))
    scores.sort()
    return scores

def mystery_a(n):                       # আপনি জানেন না এটা কী!
    total = 0
    i = n
    while i > 0:
        i //= 2
        total += i
    return total

def mystery_b(n):
    total = 0
    for i in range(n):
        j = i
        while j > 0 and n % 7 != 0:
            j -= 7
        total += j % 3
    return total

if __name__ == '__main__':
    SIZES = [250, 500, 1000, 2000, 4000]
    for name, fn in [('mystery_a', mystery_a), ('mystery_b', mystery_b)]:
        times = measure(fn, SIZES)
        ranked = classify(times, SIZES)
        print(name)
        for rank, (err, cls) in enumerate(ranked[:3]):
            tag = ' <-- verdict' if rank == 0 else ''
            print(f'   {cls:<12} max-deviation {err*100:8.2f}%{tag}')
        print()

প্রত্যাশিত output-এর আকৃতি:

mystery_a
   O(log n)     max-deviation     3.41% <-- verdict
   O(1)         max-deviation    18.90%
   O(n)         max-deviation    93.75%

mystery_b
   O(n^2)       max-deviation     6.88% <-- verdict
   O(n^3)       max-deviation    51.20%
   O(n log n)   max-deviation    58.31%

(mystery_b-র ভেতরের while প্রতি iteration-এ গড়ে constant ধাপে থামে, তাই বাইরের loop-ই dominant — classifier সেটা ধরে ফেলে। নিজের function যোগ করে খেলুন।)

নিজে বাড়ান:

O(2^n) candidate যোগ করুন আর একটা recursive Fibonacci দিয়ে test করুন — ছোট sizes-এই ratio কেমন আচরণ করে দেখুন
Measurement noise handle করতে median-of-reps নিন min-এর বদলে — noisy shared machine-এ কোনটা stable?
Ambiguous zone report করুন — verdict আর runner-up-এর deviation 5%-এর মধ্যে হলে “inconclusive, bigger n needed” ছাপুন — এটাই honest science

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

Asymptotic thinking বাস্তবে যেখানে দেখা যায়

Python-এর official wiki “TimeComplexity” page। প্রতিটা builtin operation-এর amortized/worst complexity-র টেবিল — list.append O(1) amortized, list.pop(0) O(n), dict lookup O(1) average। Production Python developer-দের সবচেয়ে বেশি চেনা asymptotic reference — এবং এর প্রতিটা entry পরের কয়েক লেসনে আমরা ভেতর থেকে বানিয়ে প্রমাণ করব।

Database query plan। EXPLAIN ANALYZE চালালে planner ঠিক এই ভাষাতেই কথা বলে: Seq Scan (Θ(n)), Index Scan (Θ(log n)), Nested Loop (Θ(n·m)), Hash Join (Θ(n+m) expected)। Index যোগ করা মানে asymptotic class বদলানো — constant tuning না। এক কোটি row-র table-এ এই পার্থক্যই “query ২ সেকেন্ড” আর “query ২ মিলিসেকেন্ড”-এর মধ্যে।

Library documentation-এর contract। C++ std::map insert-এর guarantee O(log n), std::unordered_map average O(1) — এই লেখাগুলো decorative না, standard-এর enforceable promise। API design-এ complexity guarantee-টা interface-এর অংশ: implementation বদলালেও caller-এর assumption ভাঙা যাবে না।

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

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

Asymptotically হ্যাঁ, বাস্তবে প্রায়ই না। একটা O(1) অপারেশন যদি ভেতরে hash গণনা + bucket probe + possible rehash করে, আর “O(n)“-টা হয় contiguous array-র ৩২-element linear scan — ছোট n-এ array-টা জিতবেই, cache-friendly হওয়ায় বহুগুণ জিতবে। Big-O দাবি করে n → ∞-এ কে জিতবে; n = 32-এর বিচার সেখানে নেই। এই লেসনের experiment-এই দেখেছেন — constant factor আর memory behavior ছোট n-এর রাজা। সঠিক প্রশ্ন সবসময়: আমার বাস্তব n-range-এ কে জিতবে, আর n বাড়লে crossover কোথায়?

“Algorithm-এর complexity মানেই তার runtime সেকেন্ডে।”

Runtime একটা measurement, complexity একটা mathematical property। একই Θ(n) অ্যালগরিদম Python-এ ৪০ ms, C-তে ০.৮ ms নিতে পারে — complexity একই, কারণ সেটা operation-এর গড়নের আকৃতি, সময়ের একক না। Complexity বলে: input ১০ গুণ হলে runtime কোন ঘাতে বাড়বে। Absolute সংখ্যা বের করতে চাইলে constant factor, language, hardware — তিনটাই আবার ঢুকতে হবে, আর তখন machine-independent guarantee-টা হাতছাড়া। দুটো প্রশ্ন, দুইটা আলাদা সরঞ্জাম।

“O আর Θ একই ব্যাপার — সবাই তো O-ই লেখে।”

কথ্য ব্যবহারে “O(n)” প্রায়ই Θ(n) বোঝাতেই হয়, কিন্তু technically O শুধু upper bound: linear search-কে O(n²⁰) বলাও টেকনিক্যালি সত্য আর সম্পূর্ণ অপ্রয়োজনীয়। Θ দাবি করে bound দুই দিক থেকে tight — “এর চেয়ে বেশিও না, কমও না, এই order-ই”। Lower bound দরকার হলে Ω। Interview-এ “is this tight?” জিজ্ঞেস করাটা senior signal; documentation-এ Θ লেখা সাধারণত বোঝায় লেখক পার্থক্যটা জানে।

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

O, Ω, Θ — তিনটার মধ্যে কোনটা বলে “এই খরচ এই function-এর order-এই, না কম না বেশি”? আর কেন শুধু O দিয়ে উত্তরটা অসম্পূর্ণ?

স্মরণ

Θ (big-Theta) — এটাই tight bound: upper (O) আর lower (Ω) দুই দিকেই বাঁধে। শুধু O বললে অসম্পূর্ণ কারণ upper bound অনেকগুলো হতে পারে — merge sort-কে O(n²), O(n³), O(2ⁿ) সবই বলা যায়, প্রতিটা technically true আর কোনোটাই informative না। Informative দাবিটা হলো সবচেয়ে ছোট upper bound আর সবচেয়ে বড় lower bound মিলে গেছে — সেটাই Θ।

f(n) = 3n² + 100n + 500। প্রমাণের style-এ দেখান f = Θ(n²) — অর্থাৎ উপযুক্ত c₁, c₂, n₀ খুঁজে দিন।

প্রয়োগ

Upper: 3n² + 100n + 500 ≤ 3n² + 100n² + 500n² = 503n² যখন n ≥ 1 — তাই c₂ = 503, n₀ = 1 নিলেই f ≤ c₂·n²। Lower: 3n² + 100n + 500 ≥ 3n² সব n-এ — c₁ = 3, n₀ = 0 (বা 1)। দুই দিকেই bound, তাই f = Θ(n²), আর limit check: f/n² → 3 — positive সসীম, যেমন হওয়ারই কথা।

একটা function-এর উপর doubling experiment-এ ratios পেলেন: 2.35, 2.42, 2.48 (n দ্বিগুণ করার পর পর)। Linear (ratio ≈ 2) না quadratic (≈ 4)? Classify করতে আর কী করবেন?

যুক্তি

Ratio 2-এর স্পষ্ট ওপরে, 4-এর অনেক নিচে — এটা O(n log n)-জাতীয় intermediate class-এর classic signature: ratio = 2·(log(2n)/log n), যেটা 2-এর ওপরে থেকে ধীরে 2-এর দিকে নামে। Verify করতে: (১) আরও বড় sizes-এ extend করুন — ratio-গুলো 2-এর দিকে নামছে কি না দেখুন (quadratic হলে 4-এর দিকে যেত); (২) fitting করুন — মাপা সময়গুলো n আর n·log n দুই model-এ fit করে deviation তুলনা করুন (build ঠিক এটাই করে)। Ambiguity-র সময় বড় n-ই tie-breaker — এটাই doubling method-এর জানা সীমাবদ্ধতা।

আপনার team-এ দুইটা correct implementation: A — Θ(n log n), pure C, optimized; B — Θ(n), pure Python। Input size ৫০,০০০ item, এবং সেটাই সর্বোচ্চ যে কখনো আসবে বলে মনে হচ্ছে। কোনটা ship করবেন, কোন সংখ্যাগুলো দেখে?

ডিজাইন

প্রথমে সংখ্যা দেখুন, dogma না। Rough model: C-র per-op cost Python-এর ~৫০× কম। A: 50000·log₂50000 ≈ 50000·15.6 ≈ 7.8 লক্ষ op × tiny constant। B: 50000 op × ৫০× cost ≈ 25 লক্ষ C-equivalent op — অর্থাৎ B প্রায় ৩× ধীর এই n-এ। Ship A (এছাড়া deployment simplicity-র কথাও মাথায় রাখুন)। কিন্তু decision-টা n-dependent: input যদি ১০ কোটি হতো, B-র Θ(n) win অনিবার্য হতো (crossover ≈ n·50 ≈ n·log n মানে n ≈ ২⁵⁰-এর বদলে বাস্তবে 50 ≈ log n + const → n কয়েক quadrillion — তখন B কখনোই জিতত না!)। আসল lesson: constant factor এত বড় হলে asymptotic winner বাস্তবে কখনোই overtake করে না — তাই “কোন n-range” ছাড়া complexity-based সিদ্ধান্ত অসম্পূর্ণ।

এরপর কী

আজ আমরা ভাষা পেলাম — growth-এর grammar, যেটায় দুইটা correct solution-কে machine-independent ভাবে তুলনা করা যায়। কিন্তু ভাষার একটা কঠিন প্রশ্ন এখনো ঝুলছে: list.append-এর মতো অপারেশন যার worst case প্রতি-call basis-এ O(n), সেটাকে documentation কী করে O(1) লিখে রাখে? উত্তরটা amortized analysis — অপারেশনের sequence-এর মোট খরচ ভাগ করে প্রতি-অপারেশনে ভাগ করার পদ্ধতি, তিনটা আলাদা প্রমাণ-কৌশল সহ (aggregate, accounting, potential)। পরের লেসনে dynamic array-র doubling-কে দিয়ে তিনটা পদ্ধতিই হাতে-কলমে প্রমাণ করব — মোট খরচ 3n-এর famous proof সহ — আর নিজের হাতে একটা dynamic array বানিয়ে সংখ্যাগুলো মেশিনে verify করব।

পরের লেসন: Amortized Analysis — মাঝে মাঝে দামি, গড়ে সস্তা।

Asymptotic Analysis — O, Θ, Ω: growth-এর ভাষা

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

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

আগে এটা বুঝি

মূল ধারণা

মিলিসেকেন্ড কেন মিথ্যা বলে

পাঁচটা notation — আনুষ্ঠানিক সংজ্ঞা

Best, average, worst — এক অ্যালগরিদম, তিনটা গল্প

Growth-এর সিঁড়ি — concrete সংখ্যায়

ভেতরে কী ঘটছে

Theory কী লুকায় — আর কেন তবুও কাজের

Doubling ratio — measurement থেকে class শনাক্ত

উদাহরণ

তিনটা function, হাতে-হাতে analysis

ছবিতে

Growth curve-এর আকৃতি — এক নজরে

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

Growth Lab — চারটা function, doubling ratio, আর class-fit

নিজে বানান

GrowLens — unknown function-এর complexity auto-classifier

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

Asymptotic thinking বাস্তবে যেখানে দেখা যায়

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

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

এরপর কী

এরপর কী

আরও পড়ুন

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

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

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

◆মূল ধারণাCore concept

মিলিসেকেন্ড কেন মিথ্যা বলে

পাঁচটা notation — আনুষ্ঠানিক সংজ্ঞা

Best, average, worst — এক অ্যালগরিদম, তিনটা গল্প

Growth-এর সিঁড়ি — concrete সংখ্যায়

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

Theory কী লুকায় — আর কেন তবুও কাজের

Doubling ratio — measurement থেকে class শনাক্ত

▶উদাহরণExample

তিনটা function, হাতে-হাতে analysis

◫ছবিতেDiagram

Growth curve-এর আকৃতি — এক নজরে

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

Growth Lab — চারটা function, doubling ratio, আর class-fit

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

GrowLens — unknown function-এর complexity auto-classifier

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

Asymptotic thinking বাস্তবে যেখানে দেখা যায়

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

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

→এরপর কীNext step

এরপর কী

আরও পড়ুন

আগে এটা বুঝি

মূল ধারণা

ভেতরে কী ঘটছে

উদাহরণ

ছবিতে

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

নিজে বানান

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

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

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

এরপর কী