Time, space, and amortized analysis

Complexity analysis starts by naming input variables and the operation that grows with them. Time complexity counts dominant work; space complexity counts additional memory, not always the input itself. Amortized analysis explains sequences where rare expensive operations are paid for by many cheap operations.

Trade-off: compare time, memory, and implementation complexity before committing to a structure or pattern.

On interviews: Interviewers expect you to separate best, average, and worst cases, state assumptions about hashing or sorting, and update the estimate when you add caches, recursion, or preprocessing.

Common pitfalls: Do not announce O(n) before defining n. Nested loops are not automatically O(n squared) if each pointer moves monotonically. Recursive solutions need stack space, and JavaScript recursion can hit call stack limits.

Checklist:

• Define every input variable.
• Name the dominant operation.
• Count auxiliary memory.
• Explain amortized and worst-case differences.