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
Write your first version by hand
Before opening your IDE, write your first attempt at this program on paper using Java. It does not need to be perfect.
TASK_CODE
Not marked complete. Mark it complete when your handwritten code is ready.
Open the challenge
Code Companion Local creates the starter file in the exact managed challenge folder and opens it in your preferred IDE. You do not need to create folders, files or run terminal commands.
Mark your handwritten code complete first.
If you are simply browsing the public course and are not using a class, complete the challenge in any editor you like. Code Companion Local is only needed for the connected classroom workflow.
Complete the challenge
Use your handwritten code as the starting point, then write and test your solution in the challenge workspace. Code Companion Local will ask you to compare the two versions before you submit.
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.