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

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

📏 धडा 01 — DSA का आणि Big-O: शाळा दुप्पट झाल्यावर काम कसे वाढते

📍 तुम्ही इथे आहात: 12 पैकी धडा 01 · पुढे: lesson-02-arrays

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

प्रत्येक data structure आणि प्रत्येक algorithm ज्या एका प्रश्नावर तपासला जातो तो प्रश्न: input दुप्पट झाला की काम कसे वाढते? संपूर्ण कोर्सभर तुम्ही वापराल त्या खऱ्या files:

dsa/structures.py — प्रत्येक container हाताने बनवलेला, काचेच्या भिंतींसह (आत सगळे दिसते): linked list, stack, ring-buffer queue, hash map, BST, heap, graph
dsa/algorithms.py — प्रत्येक चाल step counter सह: searches, sorts, recursion, BFS/DFS/Dijkstra, DP, greedy, two pointers
dsa/demo.py — प्रत्येक धड्यासाठी एक विभाग; प्रत्येक विभाग खर्च फक्त सांगत नाही, तो मोजतो
dsa/test_dsa.py — smoke test: सगळ्यावर 12 checks
dsa/expected-output.txt — निरोगी run काय print करतो (timings प्रत्येक machine वर वेगळ्या असतात; step counts बदलत नाहीत)

🎒 सुरू करण्याआधी: तुम्हाला फक्त Python 3 लागेल, बाकी काही नाही. Loops, lists आणि functions पुरेसे आहेत. चांगले शेजारी: Database school (indexes म्हणजे disk वरचे धडा 09 चे trees) आणि Networking school (routing म्हणजे धडा 10 चे graphs).

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

शाळेत 1,000 विद्यार्थी आहेत आणि एक नोंदवही आहे. "Dipika" शोधायला तुम्ही वरून वाचू शकता — सरासरी 500 नावे. पुढच्या वर्षी शाळा दुप्पट होते: सरासरी 1,000 नावे. हे O(n): शाळा दुप्पट, काम दुप्पट.

नोंदवही क्रमाने लावलेली असेल तर ती मधोमध उघडा: "Dipika" आधी आहे की नंतर? अर्धी फेकून द्या, पुन्हा करा — 1,000 नावांसाठी दहा नजरा, 2,000 साठी अकरा. हे O(log n): शाळा दुप्पट, फक्त एक नजर जास्त.

प्रत्येक विद्यार्थ्याचा एक कप्पा असेल आणि नावावरून कोणता कप्पा ते मोजता येत असेल, तर आकार कितीही असो, एकच नजर: O(1).

Big-O म्हणजे त्या वाढीचा आकार. सेकंद नाही, computer नाही — फक्त आकार. कोणत्याही loop चा आकार दिसू लागला की योग्य structure बहुतेक वेळा आपोआप निवडला जातो.

🗺️ आकृती

flowchart LR
  A["n = 1,000"] -->|"×2"| B["n = 2,000"]
  B --> C["O(1): same · O(log n): +1 · O(n): ×2 · O(n log n): ×2.1 · O(n²): ×4 · O(2ⁿ): squared"]

❓ काय

आकार	नाव	input दुप्पट केला →	उदाहरण
O(1)	constant	तेवढेच	`lockers[17]`, `d[key]`, push/pop
O(log n)	logarithmic	+1 step	binary search, balanced tree, heap push
O(n)	linear	×2	list scan करणे, शब्द मोजणे
O(n log n)	linearithmic	×2 आणि थोडे जास्त	merge sort, `sorted()`
O(n²)	quadratic	×4	loop च्या आत loop, bubble sort
O(2ⁿ)	exponential	वर्ग (squared)	साधा fib, प्रत्येक subset करून पाहणे

सेकंद नाही, steps मोजा. constants काढा (3n → O(n)); सर्वात मोठे पद ठेवा (n² + n → O(n²)). वेगळे सांगितले नसेल तर worst case.
Space लाही आकार असतो: merge sort ला O(n) जास्तीची जागा लागते, memo table ला O(n), जागच्या जागी swap ला O(1).
Amortised: append बहुतेक वेळा O(1) असतो, जरी array अधूनमधून copy करून वाढतो तरी — अनेक appends वर सरासरी काढल्यावर.

🤔 का

पहाटे 3 वाजता येणारा page बहुतेक वेळा आकाराचा प्रश्न असतो: दहा लाख rows वर nested loop (n²), loop मध्ये list.pop(0) (प्रत्येक pop ला n), dict हवा होता तिथे केलेला lookup. मुलाखतींमध्ये हे विचारतात कारण production याचेच बनलेले असते.

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

demo.py bigo 1k, 10k आणि 100k विद्यार्थ्यांची नोंदवही बनवतो आणि शेवटचा विद्यार्थी तीन प्रकारे शोधतो — linear, binary, hash — आणि प्रत्येकासाठी steps आणि milliseconds print करतो. step counts functions मधूनच येतात.

🧪 करून पाहा

python3 dsa/demo.py bigo
python3 dsa/test_dsa.py
python3 - <<'EOF'
import time
for n in (10_000, 20_000, 40_000):
    xs = list(range(n)); t = time.perf_counter()
    pairs = sum(1 for i in range(n) for j in range(i + 1, n, 97))   # a thinned n² loop
    print(n, f"{(time.perf_counter() - t) * 1000:.0f} ms")           # watch it ×4 each time n doubles
EOF

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

Linear steps 1,000 → 10,000 → 100,000 असे वाढतात (प्रत्येक वेळी ×10); binary steps 10 → 14 → 17 (प्रत्येक ×10 ला सुमारे +3); hash 1 वरच राहतो. n दुप्पट झाला की n² loop चा वेळ साधारण चारपट होतो. test_dsa.py OK print करतो.

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

Big-O डोळ्यांना दिसतो: तुम्ही स्वतःच्या machine वर तीन आकार वाढताना पाहिले आणि प्रत्येकाला त्याच्या वागण्यावरून नाव देऊ शकता.

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

वेगवेगळ्या machines मधले milliseconds तुलना करणे. आकारांची तुलना करा; steps मोजा.
"O(1) नेहमी O(n) पेक्षा जलद असतो." n = 5 साठी नाही. आकार मोठ्या प्रमाणावर महत्त्वाचे ठरतात.
लपलेला loop विसरणे: x in list O(n) आहे; x in set O(1) आहे.

🏭 प्रत्यक्ष वापरात हे का महत्त्वाचे: प्रत्येक scaling incident म्हणजे असा आकार जो n = 1,000 ला ठीक होता आणि n = 1,000,000 ला घातक ठरला. ship करण्याआधी आकाराला नाव देणे हे सर्वात स्वस्त performance काम आहे.

⏭️ पुढे

धडा 02 — arrays आणि strings: लॉकर्सची रांग, आणि वाचणे जलद पण मधे वाढवणे का जलद नाही.

📏 Lesson 01 — Why DSA & Big-O: how the work grows when the school doubles

📍 You are here: Lesson 01 of 12 · Next: lesson-02-arrays

📦 What's in this branch

The one question every data structure and every algorithm is answered by: how does the work grow when the input doubles? Real files you will use all the way through:

dsa/structures.py — every container built by hand with glass walls: linked list, stack, ring-buffer queue, hash map, BST, heap, graph
dsa/algorithms.py — every walk with a step counter: searches, sorts, recursion, BFS/DFS/Dijkstra, DP, greedy, two pointers
dsa/demo.py — one section per lesson; each one measures a cost instead of asserting it
dsa/test_dsa.py — the smoke test: 12 checks over everything
dsa/expected-output.txt — what a healthy run prints (timings differ per machine; the step counts do not)

🎒 Before you start: you need Python 3 and nothing else. Loops, lists and functions are enough. Good neighbours: the Database school (indexes are lesson 09's trees on disk) and the Networking school (routing is lesson 10's graphs).

🧒 Explain like I'm 5

The school has 1,000 pupils and one register. To find "Dipika" you could read from the top — on average 500 names. Next year the school doubles: 1,000 names on average. That is O(n): double the school, double the work.

If the register is sorted, open it in the middle: is "Dipika" before or after? Throw half away, repeat — ten looks for 1,000 names, eleven for 2,000. That is O(log n): double the school, one more look.

If every pupil has a pigeonhole and you can compute which one from the name, it is one look whatever the size: O(1).

Big-O is the shape of that growth. Not the seconds, not the computer — the shape. Once you can see the shape of any loop, the right structure usually picks itself.

🗺️ Diagram

flowchart LR
  A["n = 1,000"] -->|"×2"| B["n = 2,000"]
  B --> C["O(1): same · O(log n): +1 · O(n): ×2 · O(n log n): ×2.1 · O(n²): ×4 · O(2ⁿ): squared"]

❓ What

Shape	Name	Double the input →	Example
O(1)	constant	same	`lockers[17]`, `d[key]`, push/pop
O(log n)	logarithmic	+1 step	binary search, balanced tree, heap push
O(n)	linear	×2	scan a list, count words
O(n log n)	linearithmic	×2 and a bit	merge sort, `sorted()`
O(n²)	quadratic	×4	a loop inside a loop, bubble sort
O(2ⁿ)	exponential	squared	naive fib, trying every subset

Count steps, not seconds. Drop constants (3n → O(n)); keep the biggest term (n² + n → O(n²)). Worst case unless stated.
Space has a shape too: merge sort needs O(n) extra room, a memo table O(n), an in-place swap O(1).
Amortised: append is usually O(1) even though the array occasionally grows by copying — averaged over many appends.

🤔 Why

A page at 3 a.m. is usually a shape problem: a nested loop over a million rows (n²), a list.pop(0) in a loop (n per pop), a lookup that should have been a dict. Interviews ask about it because production is made of it.

🔧 How (in this repo)

demo.py bigo builds a register of 1k, 10k and 100k pupils and finds the last one three ways — linear, binary, hash — printing steps and milliseconds for each. The step counts come from the functions themselves.

🧪 Try it

python3 dsa/demo.py bigo
python3 dsa/test_dsa.py
python3 - <<'EOF'
import time
for n in (10_000, 20_000, 40_000):
    xs = list(range(n)); t = time.perf_counter()
    pairs = sum(1 for i in range(n) for j in range(i + 1, n, 97))   # a thinned n² loop
    print(n, f"{(time.perf_counter() - t) * 1000:.0f} ms")           # watch it ×4 each time n doubles
EOF

✅ Verify — what you should see

Linear steps grow 1,000 → 10,000 → 100,000 (×10 each time); binary steps 10 → 14 → 17 (about +3 per ×10); hash stays at 1. The n² loop's time roughly quadruples when n doubles. test_dsa.py prints OK.

🏁 What you just proved

Big-O is visible: you watched three shapes grow on your own machine and can name each one from its behaviour.

⚠️ Common mistakes

Comparing milliseconds between machines. Compare shapes; count steps.
"O(1) is always faster than O(n)." Not for n = 5. Shapes matter at scale.
Forgetting the hidden loop: x in list is O(n); x in set is O(1).

🏭 Why this matters in production: every scaling incident is a shape that was fine at n = 1,000 and fatal at n = 1,000,000. Naming the shape before shipping is the cheapest performance work there is.

⏭️ Next

Lesson 02 — arrays & strings: the row of lockers, and why reading is fast but growing in the middle is not.

← Course homeall lessons Next →arrays

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