Best, worst, average case — with examples — Hinglish notes

3.1.3 · Coding › Complexity Analysis

WHY do we need three cases?

HOW to compute each case (recipe)

Worked Example 1 — Linear Search

Array a[0..n-1] mein key $x$ dhundho, left se right scan karo, pehli match par ruk jao.

for i in 0..n-1:
    if a[i] == x: return i     # success
return -1                       # not found

Best case. Yeh step kyun? Sabse sasta arrangement loop ko turant band kar deta hai — a[0] == x. Ek comparison. $B (n) = 1 \in Θ (1)$

Worst case. Yeh step kyun? Sabse expensive case mein sab kuch scan karna padta hai: $x$ aakhri slot par hai, ya abhi nahin hai. Hum $n$ comparisons karte hain. $W (n) = n \in Θ (n)$

Average case (successful search, $x$ equally likely har position par). Yeh step kyun? Agar $x$ index $i$ par hai (prob $\frac{1}{n}$ ), toh cost hai $i + 1$ comparisons. Expectation lo: $A (n) = \sum_{i = 0}^{n - 1} \frac{1}{n} (i + 1) = \frac{1}{n} \sum_{k = 1}^{n} k = \frac{1}{n} \cdot \frac{n ( n + 1 )}{2} = \frac{n + 1}{2} \in Θ (n)$ Yeh step kyun? $\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2}$ (Gauss pairing). Toh average mein hum array ka lagbhag aadha scan karte hain.

Worked Example 2 — Insertion Sort (comparison count)

for i in 1..n-1:
    key = a[i]
    j = i-1
    while j>=0 and a[j] > key:   # comparison + shift
        a[j+1] = a[j]; j -= 1
    a[j+1] = key

Best case — already sorted. Yeh step kyun? Agar array ascending hai, toh while condition a[j] > key pehli test par hi false hoti hai har baar. $n - 1$ outer iterations mein se har ek mein exactly 1 comparison hota hai. $B (n) = n - 1 \in Θ (n)$

Worst case — reverse sorted. Yeh step kyun? Har naya key apne pehle ke sab elements se chhota hota hai, isliye inner loop bilkul saamne tak jaata hai. Iteration $i$ mein $i$ comparisons hote hain: $W (n) = \sum_{i = 1}^{n - 1} i = \frac{( n - 1 ) n}{2} \in Θ (n^{2})$

Average case (random permutation). Yeh step kyun? Element $i$ ke liye, average mein woh sorted prefix mein aadha andar jaata hai, jisme $\approx i /2$ comparisons lagte hain: $A (n) \approx \sum_{i = 1}^{n - 1} \frac{i}{2} = \frac{1}{2} \cdot \frac{( n - 1 ) n}{2} = \frac{n ( n - 1 )}{4} \in Θ (n^{2})$

Figure — Best, worst, average case — with examples

Worked Example 3 — Average ≠ "best+worst over 2" kyun?

Big-O / Big-Θ vs the three cases

Best-case complexity kya measure karta hai?

Fixed size

n

ke saare inputs mein se minimum operations ki count.

Worst-case complexity kya measure karta hai?

Fixed size

n

ke saare inputs mein se maximum operations — sabse unlucky arrangement.

Average-case formally define karo.

A (n) = \sum_{I} Pr (I) T (I)

, ek assumed input distribution ke under expected cost.

Best/worst/average mein kya constant rakha jaata hai?

Input size

n

; sirf input ka arrangement/content vary hota hai.

Linear search: best, worst, average comparisons?

Krama se

1

n

\frac{n + 1}{2}

Insertion sort best vs worst case order?

Best

Θ (n)

(already sorted), worst

Θ (n^{2})

(reverse sorted).

"Average = (best+worst)/2" kyun galat hai?

Average probability-weighted hota hai; midpoint ignore karta hai ki extreme inputs kitne rare/common hain (e.g. quicksort avg

Θ (n lo g n)

hai,

Θ (n^{2})

ka midpoint nahin).

Kya Big-O aur worst case same hain?

Nahin. O/Ω/Θ bound types hain; best/worst/average batate hain kaun sa input consider kar rahe ho — yeh independent hain.

In derivations mein use hua sum formula?

\sum_{k = 1}^{n} k = \frac{n ( n + 1 )}{2}

Recall Ek 12-saal ke bachche ko samjhao

Tum apni dost ko kids ki line mein dhundh rahe ho. Agar woh bilkul aage hai, toh turant mil jaati hai — yeh best case hai. Agar woh bilkul peeche hai (ya line mein hai hi nahin!), toh sabko check karna padta hai — yeh worst case hai. Agar tum yeh bahut baar karo aur average karo ki kitne bacche check kiye, toh usually aadhi line hoti hai — yeh average case hai. Line ki length same hai, par kismat decide karti hai kitna time lagta hai!

Connections

Asymptotic Notation (Big-O, Omega, Theta) — bound language jo har case express karne ke liye use hoti hai.
Linear Search aur Insertion Sort — yahan primary worked examples hain.
Quicksort — average vs worst divergence; randomized pivots.
Expected Value and Probability Distributions — average-case analysis ki foundation.
Amortized Analysis — ek alag tarah ki "averaging" (inputs par nahin, balki operations ke sequence par).

Algorithm	Best	Worst	Average
Linear search	$Θ (1)$	$Θ (n)$	$Θ (n)$
Insertion sort	$Θ (n)$	$Θ (n^{2})$	$Θ (n^{2})$
Quicksort	$Θ (n lo g n)$	$Θ (n^{2})$	$Θ (n lo g n)$