A process receives five records. It divides them into disjoint groups of two and three, visits every record in the current group once, and processes both smaller groups. A group of zero or one record stops immediately, with no counted visit. Before estimating speed, draw the calls and count this particular operation: one visit to one record during an internal call. A recursive call itself is not the operation being counted.
This is a cost model for a specified process. It does not yet say what useful result the visits compute or prove that a particular sorting or searching algorithm is correct. Correctness and cost need separate arguments.
Predict
Let C(n) be the total number of counted visits on n records. For n≥2 the smaller groups have sizes floor(n/2) and ceil(n/2). Floor rounds down, ceiling rounds up, so their sum is n even when n is odd. Predict C(5) before looking at the tree. Does every level contribute five visits? Remember that a singleton has stopped and contributes zero.
The actual operations give C(0)=C(1)=0 and, for n≥2,
C(n)=C(floor(n/2))+C(ceil(n/2))+n.
The final n counts the current call’s scan. The two recursive counts exclude that scan. For n≥2 both child sizes are smaller than n, so repeated recursion reaches a base case. The recurrence therefore determines one finite count for every nonnegative integer n.
Experiment
Edges are calls, not elapsed-time intervals. Every record belongs to exactly one group at each depth where its path continues.
Depth from root
Group sizes present
Internal-call visits
0
5
5
1
2, 3
2+3=5
2
1, 1, 1, 2
2
3
1, 1
0
Thus C(5)=12, not 15: multiplying five by the number of internal levels would count stopped singletons again. Check by recurrence: C(2)=2, C(3)=0+2+3=5, and C(5)=2+5+5=12. Now draw a changed tree for six records and predict its level totals before checking: they are 6,6,4, giving C(6)=16.
Understand
For every integer n≥1 we will prove
n floor(log₂ n) ≤ C(n) ≤ n ceil(log₂ n).
The case n=1 gives zero on both sides and must not involve division by log₂1=0. For n≥2 put k=floor(log₂ n) and h=ceil(log₂ n). A node that exists at depth j has size between floor(n/2ʲ) and ceil(n/2ʲ). To justify this, follow its path: every step rounds a half either down or up. Repeated downward rounding gives floor(n/2ʲ), repeated upward rounding gives ceil(n/2ʲ), and monotonicity bounds every mixture between them. The elementary identities for repeated halving follow by integer division, not by dropping rounding symbols.
At every depth j strictly below k, the lower bound is at least two. No path has stopped, all nodes there are internal, and disjoint group sizes sum to n. These k levels contribute exactly nk. At depth h, every existing group has size at most one, so no internal scan occurs there or deeper. Each earlier level contributes at most n because active groups are disjoint; stopped records do not appear in active groups again. There are at most h such levels, proving the upper bound nh. This proves the bounds for all integer sizes, not only powers of two.
For n≥2, x=log₂ n is at least one. Then floor(x)≥x/2 and ceil(x)≤2x, so
(1/2)n log₂ n ≤ C(n) ≤ 2n log₂ n.
These fixed constants establish Θ(n log n). Changing the logarithm base multiplies it by a fixed positive constant. Neither bound asserts that C(n) equals n log₂ n for odd n.
A sharper count is possible. For n≥2 every singleton leaf has depth h−1 or h; if n is a power of two, all are at h. Let a and b count these two types. Each record reaches exactly one singleton, giving a+b=n. Extend each shallow leaf with two placeholder children, solely for counting. All leaves of this full binary tree are now at depth h, so 2a+b=2ʰ. Therefore a=2ʰ−n and b=2n−2ʰ. Each record was visited once for every internal ancestor, so double counting gives C(n)=a(h−1)+bh=n(h+1)−2ʰ. At n=1 the same formula gives zero directly; do not invent leaves at depth −1.
Apply
Change the split to n−1 and 1 while keeping the scan. The recurrence becomes U(n)=U(n−1)+n for n≥2, with U(1)=0. Consequently U(n)=2+3+…+n=n(n+1)/2−1. For n≥2 this lies between n²/2 and n². Equal local scan costs can produce different total growth because recursion depth and subproblem sizes changed.
Repair a second error: replacing both children by ceil(n/2). At n=3 the original count is five, while the replacement gives seven. Two size-two groups cannot partition three records disjointly. A process with duplicated or padded data may have that recurrence, but it is a different process; any upper-bound comparison needs its own justification.
Finally separate counts from time. Under the original fixed rules, all inputs of the same size have the same visit count, so best- and worst-case counts agree. Measured seconds depend on implementation, memory and other operations. If record values change the branching rule, define that rule before claiming a worst-case recurrence. A finite timing table cannot prove an eventual bound.
Continue
Keep the input domain, base cases, partition, local operation and summation argument together in your solution. Reuse the asymptotic bounds lesson for quantified upper and lower bounds, and the recurrence investigation to compare a finite trace with a general proof. The practice asks for both a rounded-tree proof and changed algorithms, so recognizing the phrase “divide and conquer” is not enough.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
A call on n≥2 records partitions them into disjoint groups of sizes floor(n/2) and ceil(n/2), visits each current record once, then processes both groups. Calls on 0 or 1 records make zero counted visits. Derive the recurrence and calculate C(7) using a tree-level table, not a power-of-two substitution.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove n floor(log₂ n)≤C(n)≤n ceil(log₂ n) for every integer n≥1. Explain why level sums are n only while all nodes at that level are internal, and why no record contributes after depth ceil(log₂ n)−1.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Derive C(n)=n(h+1)−2^h for n≥2, where h=ceil(log₂ n), by counting singleton leaves of depth h−1 and h. Justify why those are the only depths and why the counts a,b satisfy a+b=n and 2a+b=2^h. Then evaluate C(13) and check n=1 separately.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Change only the partition sizes to n−1 and 1 for n≥2, still scanning all n records at each internal call. Derive U(n), solve it exactly for n≥1 and prove Θ(n²). Compare U(8) with the balanced count.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A proposed shortcut writes D(n)=2D(ceil(n/2))+n with D(1)=0 and claims it is exactly the cost of the original disjoint split. Refute the claim at n=3. Describe a process that the shortcut could count, and distinguish an upper-bound argument from an equality argument.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Give explicit constants establishing C(n)=Θ(n log₂ n) for all sufficiently large integers, using the level bounds. A report then says “therefore every input takes n log₂ n seconds, and measured small-n timings prove the worst-case theorem.” Repair each claim. What changes if a call may skip a recursive branch based on record values?
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
