Context

In Google coding interviews, you are expected not only to produce a correct solution, but also to justify its efficiency. Interviewers want to know whether your approach will scale for large inputs in systems such as Google Cloud log processing or config validation pipelines.

Core Question

Explain how you would analyze the time complexity and space complexity of a coding solution.

Your answer should address:

1. How to count work done by loops, nested loops, conditionals, and function calls.
2. How to analyze recursive solutions, including recursion depth and stack usage.
3. How to distinguish input storage from auxiliary space, and how to express the final result in Big-O notation.

Scope Guidance

Give a practical interview-style explanation rather than a purely mathematical one. You should be able to walk through a small code example, derive its runtime step by step, and explain common mistakes such as adding complexities incorrectly or ignoring hidden memory costs.