OCR A-Level Computer Science Algorithms and programming (02), June 2025: Question 2
14 marks · Hard difficulty · Extended Response
Compare the use of linear search and binary search for 50 million sorted user records referencing Big-O complexity, and explain the concept and business uses of data mining.
Practise this questionQuestion
Question text
A shopping website requires customers to create a username and password.
(a) The usernames and passwords are stored securely in a file. The file contains the username and
passwords for 50 million users which are sorted in alphabetical order by username.
The file can be searched using a linear search or a binary search.
The big-O complexities for a linear search and a binary search are given in the table:
Search Worst-case Average-case Worst-case
algorithm time time space
Linear O(n) O(n) O(1)
Binary O(log n) O(log n) O(1)
Compare the use of a linear search and a binary search in this scenario.
You should include the following in your answer:
• the features and preconditions of a linear and binary search
• the benefits and drawbacks of each search in this scenario
• a conclusion justifying which search algorithm should be used in this scenario.
You should make reference to the big-O complexities in your answer. [9]
(b) The website collects data from customers’ activities once they log on. For example, the items
they view and purchase. The company that owns the website would like to use data mining to
improve their website and customer experience.
(i) Describe what data mining means.
… [3]
(ii) Explain how the company can make use of data mining to improve their website and customer
experience.
… [2]
Mark scheme
Show the mark scheme
Question Answer Mark Guidance
2 (a) Mark Band 3 – High level 9 Answers may include, but are not limited to,
(7-9 marks) some of the points below:
The candidate demonstrates a thorough knowledge and AO1: Knowledge
understanding of binary and linear search; the material is
generally accurate and detailed. • Linear search checks each item from
the first to the last in sequence
The candidate is able to apply their knowledge and • Binary search requires data to be in
understanding directly and consistently to the context provided. order
Evidence/examples will be explicitly relevant to the • …finds middle value and compares
explanation. • …if data is less than middle repeat with
values less
The candidate provides a thorough discussion which is well • ...if data is greater than middle repeat
balanced. Evaluative comments are consistently relevant and with value greater
well-considered. • Linear worst-time and average is linear
• …grows at same rate as number of
There is a well-developed line of reasoning which is clear and elements grows
logically structured. The information presented is relevant and • Binary worst-time and average are
substantiated. logarithmic
• …grows logarithmically to number of
Mark Band 2 – Mid level elements
(4-6 marks) • Both have same worst-case space of
constant as the data is not changing
The candidate demonstrates reasonable knowledge and during the search.
understanding of binary and linear search; the material is
generally accurate but at times underdeveloped.
The candidate is able to apply their knowledge and
understanding directly to the context provided although one or
two opportunities are missed. Evidence/examples are for the
most part implicitly relevant to the explanation.
The candidate provides a reasonable discussion, the majority AO2: Application
of which is focused. Evaluative comments are, for the most
part appropriate, although one or two opportunities for • File has large number of items to search
development are missed. • …linear this will be longer worst-case
than binary
There is a line of reasoning presented with some structure. • Linear average for large number of
The information presented is in the most part relevant and items is longer than average for binary
supported by some evidence. • Data is already in order, so no additional
time required for binary to sort
Mark Band 1 – Low Level
(1-3 marks) AO3: Evaluation
The candidate demonstrates a basic knowledge of binary and • Binary is more appropriate
linear search with limited understanding shown; the material is • Data is already in order
basic and contains some inaccuracies. • Large number of items means both
worst and average time are more
The candidates makes a limited attempt to apply acquired efficient than the linear search
knowledge and understanding to the context provided.
The candidate provides a limited discussion which is narrow in
focus. Judgements if made are weak and unsubstantiated.
The information is basic and comunicated in an unstructured
way. The information is supported by limited evidence and the
relationship to the evidence may not be clear.
0 marks
No attempt to answer the question or response is not worthy of
credit.
2 (b) i 1 mark each to max 3 3
• Analysing/converting large quantities of data…
• …into useful information
• To find patterns / trends / anomalies in data
• To find information / relationships / facts not
obvious to the user
ii 1 mark each to max 2 e.g. 2 1 mark for identification; 1 mark for linked example
Identification Allow other answers that are suitable for the
• Identify patterns / trends / anomalies in their scenario stated in the question.
searches
• Identify patterns / trends / anomalies in their
purchases
Linked example
• …for example the age group purchasing specific
items
• …use this to identify adverts to give to specific
customers
• …use this to identify which items to purchase more
of
• …use this to identify the features to promote on
website
How to answer it
Search Algorithms Evaluation & Data Mining
This question evaluates your ability to critically assess search algorithms under specific system constraints and demonstrates your understanding of Big Data concepts in commercial environments:
- Algorithmic Mechanics: Operation and preconditions for linear search vs. binary search.
- Complexity Analysis: Linking Big-O time and space complexity ( O(n) , O(log n) , O(1) ) to real-world dataset sizes (50 million records).
- Extended Evaluative Writing (AO1, AO2, AO3): Constructing a balanced comparison with a justified, substantiated conclusion.
- Data Mining: Definition and practical commercial application to improve user experience.
Comparative Analysis: Linear Search vs. Binary Search
Evaluating search efficiency over 50,000,000 sorted customer records
💡 Key Knowledge (AO1)
- Linear Search: Inspects each item sequentially from first to last until a match is found or the end is reached. Works on unordered datasets.
- Binary Search: Requires data to be sorted (precondition). Finds the midpoint, compares it with the target; discards half the list and repeats on the remaining sub-list.
- Time Complexity: Linear search grows linearly ( O(n) ); binary search grows logarithmically ( O(log n) ).
- Space Complexity: Both are O(1) (constant space) for iterative implementations since no additional memory structures are created.
📐 Complexity in Practice (n = 50,000,000)
Quantifying comparisons distinguishes top-band responses:
- Linear Search (Worst Case):
Requires up to 50,000,000 comparisons ( n ). Average case: ~25,000,000 comparisons ( n/2 ). - Binary Search (Worst Case):
log₂(50,000,000) ≈ 26 comparisons maximum (since 2²⁵ ≈ 33.5M, 2²⁶ ≈ 67.1M). - Performance Impact: At 50 million users, a linear search would cause unacceptable server lag during customer login, while binary search executes almost instantaneously.
✅ Model Essay Structure (Targeting Level 3: 7–9 Marks)
1. Preconditions & Mechanics: State that linear search inspects elements one by one from index 0 to n-1 and requires no preconditions. Binary search requires the dataset to be in sorted order; it examines the median element, halving the search space in each iteration.
2. Application to Scenario (AO2): The dataset contains 50,000,000 users and is already sorted alphabetically. Because the data is already sorted, the usual disadvantage of binary search (the overhead of sorting first) does not apply.
3. Complexity Analysis:
- Linear Search: Worst/average time complexity of O(n) means runtime scales proportionally with users. Searching up to 50M items creates severe CPU load and high latency during login.
- Binary Search: Complexity of O(log n) means even for 50 million records, the worst-case search is bounded by roughly 26 comparisons.
- Space Complexity: Both operate at O(1) auxiliary space, so neither has an advantage in memory overhead.
4. Substantiated Conclusion (AO3): Conclude decisively that binary search must be chosen. The main barrier to binary search (sorting overhead) is eliminated as the file is already ordered. For 50 million records, the reduction from 25–50 million operations down to at most 26 comparisons is essential for an interactive web application.
❌ Common Errors & Pitfalls
- Ignoring the scenario: Writing generic textbook definitions without mentioning the 50 million users or alphabetical ordering.
- Claiming binary search sorts the data: Binary search does not sort; it requires data to already be sorted.
- Missing the Space Complexity: Failing to note that both algorithms have an identical space complexity of O(1) .
- Vague conclusions: Stating "both have pros and cons" without giving a clear, justified recommendation for this scenario.
🧠 Exam Technique: Securing Level 3 (7–9 marks)
- Balance all 3 bullet points: The prompt explicitly asks for preconditions/features, pros/cons, and a justified conclusion. Omitting any one caps your score in Level 2.
- Quote Big-O directly: Reference O(n) , O(log n) , and O(1) explicitly from the table provided.
- Use numbers: Approximate log₂(50×10⁶) to show the tangible difference between millions of checks vs. ~26 checks.
Definition of Data Mining
Explaining modern data processing concepts
✅ Mark Scheme Points (Any 3 for 3 marks)
- Analysing or processing large quantities of data / Big Data... [1 mark]
- ...to convert it into useful information / actionable insights. [1 mark]
- To find hidden patterns, trends, or anomalies within the data. [1 mark]
- To discover relationships, correlations, or facts not previously obvious to the user/organisation. [1 mark]
🧠 Examiner Commentary
Full marks require moving beyond simple search/retrieval. Simply writing "looking through data to find things" is too vague. You must mention large data volumes, the detection of patterns/trends/anomalies, and discovering non-obvious relationships.
❌ Common Misconception
Confusing data mining with traditional database queries (e.g. running an SQL SELECT statement). SQL retrieves known records; data mining uses algorithms to find hidden, previously unknown relationships.
Applying Data Mining to Website & Customer Experience
Identification + Linked Practical Example
✅ Model Answers (1 Mark for Identification + 1 Mark for Linked Example)
Award 1 mark for identifying the analytical use, and 1 mark for linking it to customer experience or website improvement:
- Option 1 (Targeted Recommendations): Identify trends and patterns in customer purchasing and browsing history [1 mark], and use this to display personalised product recommendations or targeted adverts on their homepage [1 mark].
- Option 2 (Stock & Inventory Management): Identify seasonal trends or spikes in item demand [1 mark], allowing the company to ensure popular items remain in stock so customers do not encounter sold-out items [1 mark].
- Option 3 (UI / Website Optimisation): Identify anomalies or bottlenecks where users frequently abandon their shopping baskets [1 mark], enabling developers to redesign the checkout flow to make it faster and smoother [1 mark].
Topics
2.1 Elements of computational thinking · 2.2 Problem solving and programming · 2.3 Algorithms · 2.1.2 Thinking ahead · 2.2.2 Computational methods · 2.3.1 Algorithms
Question and mark scheme from the OCR A-Level Computer Science examination, Algorithms and programming (02), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.