Programming technique · B2.4.1
Algorithm efficiency
Big O describes how an algorithm's required work or storage grows as its input size grows. It supports scalability decisions; it is not a stopwatch prediction.
Start by defining the input size
n is the chosen measure of how much input the algorithm receives. For an array or list, n is often the number of stored elements. You must know what n means before describing how work grows.
Time complexity
How the amount of algorithmic work grows as n grows.
Space complexity
How required storage grows as n grows.
Auxiliary space
Extra storage used by the algorithm beyond the existing input. This page labels auxiliary space explicitly.
Scalability
How well an approach continues to behave as the input becomes much larger.
Recognise four common growth patterns
| Growth class | Typical visible pattern | If n doubles... |
|---|---|---|
O(1) | A fixed amount of work independent of n | The work stays bounded. |
O(log n) | The remaining problem is repeatedly divided by a fixed factor | The number of steps grows only slightly. |
O(n) | One complete traversal of n items | The dominant work roughly doubles. |
O(n^2) | A full n-by-n nested traversal | The dominant work roughly quadruples. |
Keep the dominant growth
3n + 5
The linear term grows with the input; the fixed addition and constant multiplier do not change the growth class. Result: O(n).
n² + n
The quadratic term dominates the linear term as the input grows. Result: O(n²).
Time and space are different resources
A method can use O(1) auxiliary space while still taking O(n) time. A copied collection can raise auxiliary space to O(n) even when both approaches visit each input item once.
Check your understanding
Answer each question before opening the model answer.
-
A loop visits every one of n values once. What is its time complexity?
Reveal model answer
O(n), because the repeated work grows directly with the number of input values.
-
Two loops are nested, but the inner loop always runs exactly 5 times. Is the result automatically O(n²)?
Reveal model answer
No. If the outer loop runs n times and the inner loop is fixed at 5 repetitions, the work is 5n, which simplifies to O(n).
-
Why is repeated halving associated with O(log n)?
Reveal model answer
Each step removes a fixed fraction of the remaining problem, so multiplying the input by a fixed factor adds only a small number of extra steps.
-
Does O(n) guarantee a program is faster than O(n²) for every tiny input?
Reveal model answer
No. Big O describes growth for increasing input sizes; constants, implementation details and the particular small input still affect measured runtime.
Choose using the actual constraint
A lower-growth algorithm is generally more scalable for large inputs, but a justified choice should name the relevant resource: time, extra memory, existing data order, implementation complexity or another stated requirement. “More efficient” without saying what is being saved is incomplete.
Challenges Choose one
Choose a challenge that feels appropriate for you. Code heat is only a rough estimate, not a fixed level.
Growth Counter
SelectedCreate four small methods that expose constant, linear, repeated-halving and quadratic work. Add an operation counter to each one and run them for several input sizes such as 8, 16 and 32. Record the counts, identify the dominant growth and state the tightest familiar Big O class supported by the code. Explain why the measured operation counts are evidence of growth rather than clock time.
Time and Space Trade-off
SelectedWrite one method that processes an integer array using only a fixed number of extra variables and another that creates an additional array whose size grows with the input. For each method, identify n, calculate the time complexity and auxiliary-space complexity, and explain which design better fits a scenario with a strict memory limit.
Scalability Decision
SelectedCreate two clearly different approaches to the same simple counting problem: one using a single traversal and one using a full nested traversal. Use operation counts for increasing n to support O(n) and O(n^2), then write a short scenario-based judgement about scalability. Include one limitation of using Big O alone when comparing real programs.
Selected challenge
This choice is shared with the portfolio setup page.
Plan your solution in handwritten pseudocode
Before opening your IDE or writing any program code, handwrite pseudocode for this challenge on paper.
Not marked complete. If you submit now, the GitHub README will record “No”.
Create your challenge folder
Run this command after planning. It creates the correct empty folder inside your portfolio.
Complete the challenge
Use your handwritten pseudocode as the starting plan, then write and test your solution in the folder created above.
Optional two-level scaffold
Try from your handwritten pseudocode first. Scaffold gives some structure; Scaffold + comments gives stronger guidance. Use only the level you need, and update your pseudocode first if the support changes your plan.
Submit for review
Run this when your program is complete. It creates the README, commits the folder and pushes it. The README records whether you marked the handwritten pseudocode as complete; the paper itself is handed to your teacher separately.