🖼️ See the drawing + lab 🏠 Course home 🌿 Branch on GitHub ✏️ View source

🖼️ आकृती आणि labThe drawing + lab पूर्ण पानावर उघडा ↗Open full page ↗

📈 धडा 04 — प्रत्यक्षातली complexity: जोडी-जोडीने, की आधी sort?

📍 तुम्ही इथे आहात: 12 पैकी धडा 04 · मागे: lesson-03-profiling · पुढे: lesson-05-memory

📦 या ब्रँचमध्ये काय आहे

धडे 01–03, अधिक algorithmic complexity, पाठ करून नव्हे तर मोजून: एकच प्रश्न — "कोणते bib क्रमांक दोनदा आले आहेत का?" — तीन प्रकारे सोडवलेला, प्रत्येक comparison मोजून: प्रत्येक जोडी (O(n²)), आधी sort करून मग शेजारी तपासणे (O(n log n)), आणि set (सरासरी O(n)). perf/demo.py मधले complexity() आणि perf/sim.py मधले dup_pairs, dup_sorted, merge_sort आणि dup_set.

🧒 5 वर्षांच्या मुलाला समजावल्यासारखे

शर्यतीआधी प्रत्येक धावपटूला एक bib क्रमांक मिळतो. 🔢 दोन धावपटूंचा क्रमांक कधीच सारखा असता कामा नये. ऐश्वर्याला हे तपासायचे आहे.

पद्धत 1 — प्रत्येक जोडी: धावपटू 1 घ्या, त्याची प्रत्येक इतर धावपटूशी तुलना करा. मग धावपटू 2 ची त्यानंतरच्या प्रत्येकाशी. असेच पुढे. 250 धावपटूंसाठी 31,125 तपासण्या. 2000 धावपटूंसाठी जवळजवळ 2 million. प्रत्येक वेळी शाळा दुप्पट होते, तेव्हा काम चौपट होते. 😵
पद्धत 2 — आधी sort: धावपटूंना bib क्रमांकानुसार रांगेत उभे करा. आता कोणतेही दोन सारखे क्रमांक एकमेकांच्या शेजारीच उभे असले पाहिजेत. Sort करायला काही तपासण्या लागतात, मग रांगेवरून एकदा नजर. 2000 धावपटूंसाठी: सुमारे 21,000 तपासण्या.
पद्धत 3 — खुणांचा कागद: प्रत्येक संभाव्य क्रमांकासाठी एक चौकोन असलेला कागद. प्रत्येक धावपटूसाठी, त्याचा चौकोन पाहा: आधीच खूण आहे? दुहेरी! नसेल, तर खूण करा. प्रत्येक धावपटूसाठी एक नजर: 2000.

प्रत्येक पद्धतीचे उत्तर एकच. कामाचे प्रमाण मात्र खूप वेगवेगळे.

🗺️ आकृती

flowchart LR
    q["❓ any duplicate bib<br/>among n runners?"] --> a["every pair · O(n²)<br/>n = 2000 → 1,999,000"]
    q --> b["sort + neighbours · O(n log n)<br/>n = 2000 → 21,436"]
    q --> c["a set · O(n)<br/>n = 2000 → 2,000"]
    a --> g["double n → 4× the work"]
    b --> h["double n → a bit over 2×"]
    c --> i["double n → 2×"]

🗺️ काढलेली आकृती + एक lab: https://school-edh.pages.dev/performance/lesson-diagrams.html#l04

❓ काय

Big-O — input वाढल्यावर काम कसे वाढते ते, constant factors दुर्लक्षित करून. O(n): input दुप्पट, काम दुप्पट. O(n²): input दुप्पट, काम चौपट. O(n log n): दुप्पटीपेक्षा थोडे जास्त. ते एका आकारासाठी लागणारा वेळ सांगत नाही — फक्त वाढीचा आकार सांगते.
Worst, average आणि best case — lab च्या bibs मध्ये एकही दुहेरी क्रमांक नाही, म्हणून प्रत्येक पद्धत आपले पूर्ण काम करते (worst case). दुहेरी क्रमांक असेल, तर पद्धत लवकर थांबू शकते.
प्रत्येक जोडी — n(n−1)/2 comparisons. n = 2000 वर: 1,999,000.
Sort + शेजारी — lab असा merge sort वापरते जो आपली comparisons मोजतो (सुमारे n·log₂n), मग n−1 शेजारी-तपासण्या. Python चे स्वतःचे sorted() (Timsort, आणि 3.11 पासून "powersort" merge policy सह) सुद्धा O(n log n) आहे, आणि आधीच अंशतः sorted असलेल्या data वर खूप जलद आहे.
Hash set — x in some_set ला आकार कितीही असला तरी साधारण तेवढाच खर्च येतो (सरासरी O(1); अनेक hash collisions त्याला हळू करू शकतात). म्हणून एक pass सरासरी O(n) आहे.
नेहमीचा लपलेला O(n²) — दुसऱ्या list वरच्या loop च्या आत if x in some_list. प्रत्येक in list चाळतो. ते एका ओळीसारखे दिसते; प्रत्यक्षात loop च्या आत loop आहे. धडा 03 मधले find_runner हेच होते.
Constants अजूनही महत्त्वाचे — लहान n साठी, कमी overhead असलेला "वाईट" algorithm जिंकू शकतो. Big-O सांगते n मोठा झाल्यावर काय होते — आणि तेव्हाच तुम्हाला काळजी असते.

यामागची data structures (sorting, hashing, trees) हा DSA school चा विषय आहे.

🤔 का

कारण कितीही tuning केले तरी चुकीचा algorithm वाचत नाही. जोडी-जोडीचा loop दुप्पट जलद केल्याने शाळेचा आकार फक्त एकदा दुप्पट होईपर्यंत वेळ मिळतो; त्यानंतर तो पुन्हा हळू होतो. O(n²) बदलून O(n log n) केल्याने संपूर्ण वक्ररेषाच बदलते. आणि complexity bugs tests मध्ये लपतात: 20 rows वर प्रत्येक पद्धत क्षणात होते. ते production मध्ये दिसतात, ज्या दिवशी data मोठा होतो.

🔧 कसे (या repo मध्ये)

perf/sim.py मधले bibs(n) seeded random क्रमाने n वेगवेगळे क्रमांक देते. dup_pairs प्रत्येक जोडीची तुलना करते; dup_sorted merge_sort(xs, count) call करते — एक साधा merge sort जो प्रत्येक comparison साठी count[0] मध्ये 1 जोडतो — मग शेजारी तपासते; dup_set प्रत्येक item साठी एक set lookup करते. प्रत्येक (found a duplicate?, comparisons) परत देते. perf/demo.py मधले complexity() n ला 250 पासून 2000 पर्यंत दुप्पट करत जाते.

🧪 करून पाहा

python3 perf/demo.py complexity
python3 - <<'EOF'
import math, sys; sys.path.insert(0, "perf"); from sim import bibs, dup_pairs, dup_sorted
for n in (1000, 2000, 4000):
    b = bibs(n); srt = dup_sorted(b)[1]
    print(f"n {n:>5}: every pair n(n-1)/2 = {n * (n - 1) // 2:>9,} · merge sort + scan {srt:>6,} · n·log2(n) = {round(n * math.log2(n)):>6,}")
b = bibs(1000); b[700] = b[3]
print("with one duplicate: every pair", dup_pairs(b), "· sorted", dup_sorted(b))
EOF

✅ तपासा — तुम्हाला काय दिसायला हवे

complexity हे छापते:

       n   every pair O(n²)   sort + neighbours O(n log n)   a set O(n)
     250             31,125                          1,921          250
     500            124,750                          4,355          500
    1000            499,500                          9,724        1,000
    2000          1,999,000                         21,436        2,000
   double n: every pair does 4× the work · sorting a little over 2× · the set exactly 2×
   big-O is how the work GROWS; at n = 2000 the pairwise way already does 93× the comparisons of sorting

तुमचा snippet हे छापतो:

n  1000: every pair n(n-1)/2 =   499,500 · merge sort + scan  9,724 · n·log2(n) =  9,966
n  2000: every pair n(n-1)/2 = 1,999,000 · merge sort + scan 21,436 · n·log2(n) = 21,932
n  4000: every pair n(n-1)/2 = 7,998,000 · merge sort + scan 46,873 · n·log2(n) = 47,863
with one duplicate: every pair (True, 3691) · sorted (True, 9439)

🏁 तुम्ही आत्ताच काय सिद्ध केले

Counts सूत्रांनुसारच येतात: प्रत्येक जोडी म्हणजे नेमके n(n−1)/2, आणि merge sort n·log₂n च्या किंचित खाली राहतो. 250 ते 2000 धावपटू (8× जास्त), जोडी-जोडीच्या पद्धतीने 64× जास्त काम केले, sort ने सुमारे 11×, set ने 8×. मुद्दाम ठेवलेल्या दुहेरी क्रमांकासह, जोडी-जोडीची पद्धत 3,691 comparisons नंतर थांबली — इथे नशीब चांगले होते, कारण दुहेरी क्रमांक सुरुवातीजवळ होता; तुम्ही नशिबावर अवलंबून राहू शकत नाही.

⚠️ नेहमीच्या चुका

loop च्या आत if item in a_list — membership साठी set किंवा dict वापरा
loop च्या आत sort करणे (एकदाच, बाहेर sort करा)
test data च्या 10 rows वरून algorithm ची परीक्षा घेणे
ज्या languages मध्ये loop मध्ये += ने string बनवल्यास प्रत्येक वेळी संपूर्ण string copy होते तिथे तसे करणे (Python मध्ये, तुकडे list मध्ये गोळा करा आणि "".join करा)
जिथे n नेहमीच लहान असतो तिथे complexity च्या मागे लागणे — आधी profile करा (धडा 03)

🏭 प्रत्यक्ष वापरात

दुपटीच्या test ने काम कसे वाढते ते तपासा: काम n, 2n आणि 4n वर मोजा (वेळ किंवा count). जर प्रत्येक दुपटीला सुमारे 4× जास्त वेळ लागत असेल, तर कुठेतरी O(n²) आहे. खऱ्या machine वर:

for n in 1000 2000 4000; do
  python3 -c "import time; xs=list(range($n)); t=time.perf_counter(); [x for x in xs if x in xs]; print($n, round(time.perf_counter()-t, 3), 's')"
done      # x in a list, inside a loop: each doubling ≈ 4× the time

काम कमी ठेवणारी standard-library tools:

import bisect, heapq
from collections import Counter
dupes = [b for b, c in Counter(bibs).items() if c > 1]   # O(n) with a hash map
top10 = heapq.nsmallest(10, laps)                        # O(n log 10), no full sort
i = bisect.bisect_left(sorted_bibs, 1234)               # O(log n) lookup in sorted data

🏭 Production मध्ये हे का महत्त्वाचे आहे: जेव्हा एखाद्या job चा वेळ त्याच्या data पेक्षा जास्त वेगाने वाढतो, तेव्हा loop च्या आतला loop शोधा — बऱ्याचदा list वरचा in, प्रत्येक row साठी एक query, किंवा प्रत्येक item साठी एक sort.

⏭️ पुढे

वेळ हा एक खर्च आहे. Memory हा दुसरा: सगळे एकदम धरून ठेवणे, की एका वेळी एक item. पुढे: lists, generators आणि tracemalloc.

git checkout lesson-05-memory

📈 Lesson 04 — Complexity in practice: pair by pair, or sort first?

📍 You are here: Lesson 04 of 12 · Previous: lesson-03-profiling · Next: lesson-05-memory

📦 What's in this branch

Lessons 01–03, plus algorithmic complexity, measured instead of recited: the same question — "are there any duplicate bib numbers?" — answered three ways, with every comparison counted: every pair (O(n²)), sort then check neighbours (O(n log n)), and a set (O(n) on average). complexity() in perf/demo.py and dup_pairs, dup_sorted, merge_sort and dup_set in perf/sim.py.

🧒 Explain like I'm 5

Before the race, every runner gets a bib number. 🔢 Two runners must never have the same one. Aishwarya has to check.

Way 1 — every pair: take runner 1, compare with every other runner. Then runner 2 with every runner after. And so on. With 250 runners that is 31,125 checks. With 2000 runners it is almost 2 million. Every time the school doubles, the work goes up four times. 😵
Way 2 — sort first: line the runners up by bib number. Now any two equal numbers must stand next to each other. Sorting takes some checks, then one look along the line. With 2000 runners: about 21,000 checks.
Way 3 — a tick sheet: a sheet with a box for every possible number. For each runner, look at their box: already ticked? Duplicate! If not, tick it. One look per runner: 2000.

Same answer every way. Very different amounts of work.

🗺️ Diagram

flowchart LR
    q["❓ any duplicate bib<br/>among n runners?"] --> a["every pair · O(n²)<br/>n = 2000 → 1,999,000"]
    q --> b["sort + neighbours · O(n log n)<br/>n = 2000 → 21,436"]
    q --> c["a set · O(n)<br/>n = 2000 → 2,000"]
    a --> g["double n → 4× the work"]
    b --> h["double n → a bit over 2×"]
    c --> i["double n → 2×"]

🗺️ Drawn version + a lab: https://school-edh.pages.dev/performance/lesson-diagrams.html#l04

❓ What

Big-O — how the work grows as the input grows, ignoring constant factors. O(n): double the input, double the work. O(n²): double the input, four times the work. O(n log n): a bit more than double. It does not tell you the time for one size — only the shape of the growth.
Worst, average and best case — the lab's bibs have no duplicate, so every method does its full work (worst case). With a duplicate, a method can stop early.
Every pair — n(n−1)/2 comparisons. At n = 2000: 1,999,000.
Sort + neighbours — the lab uses a merge sort that counts its comparisons (about n·log₂n), then n−1 neighbour checks. Python's own sorted() (Timsort, and since 3.11 with a "powersort" merge policy) is also O(n log n), and much faster on data that is already partly sorted.
Hash set — x in some_set costs about the same whatever the size (O(1) on average; many hash collisions can make it slower). So one pass is O(n) on average.
The classic hidden O(n²) — if x in some_list inside a loop over another list. Each in walks the list. It looks like one line; it is a loop inside a loop. Lesson 03's find_runner was the same thing.
Constants still matter — for small n, a "worse" algorithm with less overhead can win. Big-O tells you what happens when n gets big — which is when you care.

The data structures behind these (sorting, hashing, trees) are the DSA school.

🤔 Why

Because no amount of tuning saves the wrong algorithm. Making the pairwise loop twice as fast buys you one doubling of the school size; after that, it is slow again. Changing O(n²) to O(n log n) changes the whole curve. And complexity bugs hide in tests: on 20 rows every method is instant. They appear in production, on the day the data gets big.

🔧 How (in this repo)

bibs(n) in perf/sim.py gives n different numbers in a seeded random order. dup_pairs compares every pair; dup_sorted calls merge_sort(xs, count) — a plain merge sort that adds 1 to count[0] per comparison — then checks neighbours; dup_set does one set lookup per item. Each returns (found a duplicate?, comparisons). complexity() in perf/demo.py doubles n from 250 to 2000.

🧪 Try it

python3 perf/demo.py complexity
python3 - <<'EOF'
import math, sys; sys.path.insert(0, "perf"); from sim import bibs, dup_pairs, dup_sorted
for n in (1000, 2000, 4000):
    b = bibs(n); srt = dup_sorted(b)[1]
    print(f"n {n:>5}: every pair n(n-1)/2 = {n * (n - 1) // 2:>9,} · merge sort + scan {srt:>6,} · n·log2(n) = {round(n * math.log2(n)):>6,}")
b = bibs(1000); b[700] = b[3]
print("with one duplicate: every pair", dup_pairs(b), "· sorted", dup_sorted(b))
EOF

✅ Verify — what you should see

complexity prints:

       n   every pair O(n²)   sort + neighbours O(n log n)   a set O(n)
     250             31,125                          1,921          250
     500            124,750                          4,355          500
    1000            499,500                          9,724        1,000
    2000          1,999,000                         21,436        2,000
   double n: every pair does 4× the work · sorting a little over 2× · the set exactly 2×
   big-O is how the work GROWS; at n = 2000 the pairwise way already does 93× the comparisons of sorting

Your snippet prints:

n  1000: every pair n(n-1)/2 =   499,500 · merge sort + scan  9,724 · n·log2(n) =  9,966
n  2000: every pair n(n-1)/2 = 1,999,000 · merge sort + scan 21,436 · n·log2(n) = 21,932
n  4000: every pair n(n-1)/2 = 7,998,000 · merge sort + scan 46,873 · n·log2(n) = 47,863
with one duplicate: every pair (True, 3691) · sorted (True, 9439)

🏁 What you just proved

The counts follow the formulas: every pair is exactly n(n−1)/2, and the merge sort stays just under n·log₂n. From 250 to 2000 runners (8× more), the pairwise way did 64× more work, the sort about 11×, the set 8×. With a planted duplicate, the pairwise way stopped after 3,691 comparisons — lucky here, because the duplicate was near the front; you cannot count on luck.

⚠️ Common mistakes

if item in a_list inside a loop — use a set or dict for membership
sorting inside a loop (sort once, outside)
judging an algorithm on 10 rows of test data
string building with += in a loop in languages where it copies the whole string each time (in Python, collect pieces in a list and "".join them)
chasing complexity where n is always tiny — profile first (lesson 03)

🏭 In production

Check how work grows with a doubling test: time (or count) the job at n, 2n and 4n. If each doubling takes about 4× longer, you have an O(n²) somewhere. On a real machine:

for n in 1000 2000 4000; do
  python3 -c "import time; xs=list(range($n)); t=time.perf_counter(); [x for x in xs if x in xs]; print($n, round(time.perf_counter()-t, 3), 's')"
done      # x in a list, inside a loop: each doubling ≈ 4× the time

Standard-library tools that keep work small:

import bisect, heapq
from collections import Counter
dupes = [b for b, c in Counter(bibs).items() if c > 1]   # O(n) with a hash map
top10 = heapq.nsmallest(10, laps)                        # O(n log 10), no full sort
i = bisect.bisect_left(sorted_bibs, 1234)               # O(log n) lookup in sorted data

🏭 Why this matters in production: when a job's time grows faster than its data, look for a loop inside a loop — often an in on a list, a query per row, or a sort per item.

⏭️ Next

Time is one cost. Memory is the other: holding everything at once, or one item at a time. Next: lists, generators and tracemalloc.

git checkout lesson-05-memory

← Previousprofiling Next →memory

This page is the lesson's README from the lesson-04-complexity branch, shown here so the whole School stays on one site. Code files open on GitHub at the same branch.