0/6 traced
Linear recursion
One call reduces n by one, then unwinds. T(n) = T(n - 1) + O(1)
worst case O(n) time O(n) space
1int sum(int n) {2if (n <= 1) return n;3int child = sum(n - 1);4return n + child;5}
Runtime call stackcall
Recursion levels
L01 call
L11 call
L21 call
L31 call
L41 call
Execution recurrenceT(n) = T(n - 1) + O(1)
- Total calls
- 1
- Completed
- 0
- Maximum depth
- 1
- Repeated subproblems
- 0
- Total work
- 1
- Latest return
- —
Exact work through this line 1 +2 on this line
O(n) time O(n) auxiliary space 1 peak return values
1comparisons
0reads
0writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
1calls
0returns
Variables before line
Variables after line
Reads, writes, and state changes on this line
No state write; this line performs control flow or a read.
Why this bound?
O(n) time · O(n) space
worstnode 1node 2node 3node 4node 5 Work can grow once per node → n
Auxiliary memory model
frame 1frame 2frame 3frame 4frame 5
Recursive calls remain live together, so peak call-stack depth grows with n.
- The execution creates 5 calls across 5 levels.
- Maximum live stack depth is 5; widest level has 1 calls.
- T(n) = T(n - 1) + O(1) resolves to O(n) time for this scenario.
Assumptions behind this claim
- Each call, return, base test, and displayed local-work unit is counted.
- Input is capped at 12 to keep the execution tree readable.
Step 1 of 11 · call Call with n = 5
Push a frame at depth 1; the base-case test runs before any child call.
About this implementation
Every displayed recurrence is backed by the call and return events in this trace. Language switching preserves the active semantic event, stack, counters, and recurrence.