DAA — Cost From Code (Loops + Recurrence Playground)

Loop Pattern Playground

Goal: iteration count → Big-O

Choose a common pattern

Input size n

Slider is for intuition; asymptotic ignores constants.

Show counting steps

Result

—

Representative C snippet

updates with dropdown

Rule of thumb

Independent nested loops → multiply counts.
Dependent nested loops → summation (Σ).
Updates like j*=2 or j/=2 → log n.
Conditions like i*i ≤ n → √n.

Recurrence Builder (from code thinking)

Ask 3 questions

1) # recursive calls (a)

Merge sort: a=2

2) shrink factor (b)

Binary search: b=2

3) work outside recursion f(n)

Typically loops / merge / partition cost inside one call.

Built recurrence

—

Teaching script (say this aloud)

Each call creates a subcalls of size n/b.
Extra non-recursive work is f(n).
Stop at base: T(1)=Θ(1).

Example code (click to load)

recurrence = calls + local work

Click an example…

Mini-checklist

Count subcalls (a).
New size per call (n/b).
Local work (f(n)).
Base case (T(1)).

Solve: T(n)=aT(n/b)+f(n)

Master Theorem

f(n)

Verdict

—

Recursion Tree table (first levels)

intuition builder

Teacher line

“Compare f(n) with n^{log_b a}.” If balanced, multiply by log levels.

Quick Check

Score: 0 / 5

Q1) Outer loop runs n times, inner doubles: for(j=1; j<=n; j*=2)

—

Q2) Triangle loop: for(i=1..n) for(j=1..i) work()

—

Q3) Recurrence: T(n)=T(n/2)+Θ(1)

—

Q4) Merge sort: T(n)=2T(n/2)+Θ(n)

—

Q5) Recurrence: T(n)=T(n/2)+Θ(n)

—

Exam mantra

Doubling/halving loops → log n
Dependent loops → Σ (summation)
Master theorem core: compare f(n) vs n^{log_b a}
T(n)=T(n/2)+n → geometric sum → Θ(n)

Add this page to Index

Place it in Module-1 (Asymptotics) after “Asymptotic Notations”.

<a class="btn btn-primary" href="09_cost_from_code.html">
  Cost From Code (Loops + Recurrence)
</a>

Cost From Code — Loops + Recurrence Playground