A Level Computer Science OCR Practice Exam

Which type of complexity increases equally to the number of data objects an algorithm processes?

1. Quadratic Complexity

2. Logarithmic Complexity

3. Linear Complexity

4. Constant Complexity

The correct answer is: Linear Complexity

The answer is indeed linear complexity, which is characterized by an increase in the time or space required by an algorithm that grows directly in proportion to the amount of input data being processed. In practical terms, if an algorithm has linear complexity, doubling the number of data objects will roughly double the time or space needed to complete the operations, leading to a straightforward, predictable scaling of performance. This contrasts with other complexities where the growth rate is not directly proportional. For example, quadratic complexity signifies that if the input size doubles, the time taken increases by a factor of four, indicating a significantly steeper increase. Logarithmic complexity, on the other hand, suggests a much slower growth rate as the input size expands; processes that exhibit this complexity increase by logarithmic factors, which is much smaller than linear growth. Constant complexity indicates that the performance remains the same regardless of the input size, meaning the algorithm takes a fixed amount of time or space regardless of the number of data objects. Understanding these complexities helps in choosing the right algorithm based on expected input size, as linear complexity is often desirable for scalability.