← DSA I

Character execution laboratory

Strings Lab

0/9 traced
Presets

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++;
3
4
5return 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

worst
node 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.

  1. The trace processes at most n characters.
  2. 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.

1 / 7