Tracing a Nested Loop with Integer Division
Consider this C function:
int f(int n) { int s = 0; for (int i = 1; i <= n; i += 2) { for (int j = i; j > 0; j /= 2) { s += j % 3; } } return s; }
The function is compiled with a standard C compiler where int is 32-bit and division of positive integers truncates toward zero. A candidate traces f(6) by hand and gets 5, but a teammate gets 7. The disagreement arises from whether the inner loop runs for j = 1 and from how many times j is halved. Before using the function in a scoring module, the team needs a reliable trace, a growth-rate estimate, and a check for negative n. Assume n is a non-negative integer for the first two tasks.
1. Trace f(6) exactly, showing each value of i and j and the running sum.
Read the worked answer
i takes 1, 3, 5 because i <= 6 and i += 2.
- i=1: j=1 gives 1%3=1, so s=1; j becomes 0 and the inner loop stops.
- i=3: j=3 gives 0, s=1; j=1 gives 1, s=2; j=0 stops.
- i=5: j=5 gives 2, s=4; j=2 gives 2, s=6; j=1 gives 1, s=7; j=0 stops.
Return 7. The answer 5 probably comes from omitting the j=1 iteration for i=5 or one of the j=1 iterations for i=3.
2. Give the tightest Big-O growth of f(n) in terms of n, with justification.
Read the worked answer
The outer loop runs about n/2 times. For a given i, the inner loop starts at j=i and halves j until 0, so it runs floor(log2 i) + 1 times. Total work = sum over odd i <= n of O(log i) = O(n log n), because there are O(n) outer iterations and each has O(log n) inner steps. The sum is asymptotically about (n/2) log n. It is not O(n), because log i grows, and O(n^2) is not tight. Space is O(1).
3. For n=10, compute f(10). Then state what f returns for n = -3 and why.
Read the worked answer
For n=10, i=1,3,5,7,9.
- i=1: j=1 adds 1, total 1.
- i=3: j=3 adds 0; j=1 adds 1; total 2.
- i=5: j=5 adds 2; j=2 adds 2; j=1 adds 1; subtotal 5, total 7.
- i=7: j=7 adds 1; j=3 adds 0; j=1 adds 1; subtotal 2, total 9.
- i=9: j=9 adds 0; j=4 adds 1; j=2 adds 2; j=1 adds 1; subtotal 4, total 13.
So f(10)=13. For n=-3, the outer loop condition i <= n is 1 <= -3, which is false at initialization, so the body never runs and f returns 0. No undefined behavior occurs because i is initialized and compared before use.