0/9 traced
Search
Scan for the first matching character.
worst case O(n) time O(1) space
1size_t i = 0;2while (i < source.size() && source[i] != target) i++;345return i < source.size() ? i : -1;
Character memory6 source cells
Source
0R
1E
2P
3L
4A
5Y
Second / target
0A
Intermediate result∅
- Allocations
- 0
- Character copies
- 0
- Builder capacity
- —
- Found index
- not found
Exact work through this line 1 +1 on this line
O(n) time O(1) auxiliary space 0 peak characters
0comparisons
1reads
0writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line
resultnull
Variables after line
resultnull
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(1) space
worstnode 1node 2node 3node 4node 5node 6 Work can grow once per node → n
Auxiliary memory model
cursortemporarycounter
A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- The trace processes at most n characters.
- A constant amount of work per character gives O(n).
Assumptions behind this claim
- Strings use indexed contiguous character storage.
- Character reads, writes, comparisons, and allocations are counted directly.
Step 1 of 7 · setup Prepare the operation
The source contains 6 characters.
About this implementation
The same semantic step drives C, C++, Java, and Python. Switching language changes only the source representation; the character cells, trace cursor, and work counters stay fixed.