Complexity describes how resource use grows with input size. State which variable represents input and distinguish worst-case bounds from amortized behavior.
Before you start
You should know arrays, loops and basic complexity notation. Start with a small input you can trace by hand. State what each variable means and which invariant is maintained, then use that invariant to explain correctness before discussing performance or writing a more compact solution.
The practical goal is to reason through this situation: A nested loop over two independent inputs costs O(nm), not automatically O(n squared). Read the walkthrough first, then try the interview exercise before opening its answer. The important part is explaining the decision and its consequences, rather than remembering a definition alone.
Step-by-step walkthrough
Step 1: Define input variables
Use n and m for independently sized collections.
Step 2: Count actual iterations
Sequential work adds; nested work multiplies only when bounds justify it.
Step 3: State the model
Distinguish worst-case, expected and amortized claims.
Worked scenario
A nested loop over two independent inputs costs O(nm), not automatically O(n squared).
A loop visiting n users followed by m orders performs n+m visits. A loop visiting every order for every user performs nm visits. A triangular loop performs 1+2+…+n visits, still quadratic even though it does not execute exactly n squared iterations.
Common mistake
Counting loop syntax without following bounds produces incorrect estimates.
Verify the behavior
Double each input independently and predict how work changes for each loop shape.
Interview exercise
Analyze two separate sequential loops.
Answer and reasoning
Their work adds: O(n+m). Nested dependent loops require summing the actual iteration counts.
Continue learning
Compare the scenario with the Data Structures and Algorithms interview questions and test your understanding with the Data Structures and Algorithms MCQs. For terminology and implementation details, consult the reference material.