GATE CS 2005 Q31 — Asymptotic Worst Case Time and Space Complexity

To find the output of the program, we trace the execution step-by-step:

1. Pass-by-Value Behavior: In C, arguments are passed by value. The variable sum in main() is passed to foo(). Any modifications to sum inside foo() are local to the activation records of foo() and do not affect the variable sum in main(). Thus, the final printf("%d\n", sum) in main() will print 0.
2. Tracing the Recursion:
   • foo(2048, 0): $k = 8$, $j = 204$, local $sum = 8$. Calls foo(204, 8). Prints $8$ after returning.
   • foo(204, 8): $k = 4$, $j = 20$, local $sum = 12$. Calls foo(20, 12). Prints $4$ after returning.
   • foo(20, 12): $k = 0$, $j = 2$, local $sum = 12$. Calls foo(2, 12). Prints $0$ after returning.
   • foo(2, 12): $k = 2$, $j = 0$, local $sum = 14$. Calls foo(0, 14). Prints $2$ after returning.
   • foo(0, 14): Base case reached ($n == 0$), returns immediately.

As the recursion unwinds, the printf statements execute in reverse order of the calls (Last-In, First-Out):

• foo(2, 12) prints 2,
• foo(20, 12) prints 0,
• foo(204, 8) prints 4,
• foo(2048, 0) prints 8,

Finally, main() prints the original value of sum, which is 0. Thus, the complete output is 2,0,4,8,0.