A Level Computer Science OCR Practice Exam

What complexity defines an algorithm that remains the same regardless of the size of the data set?

1. Linear Complexity

2. Constant Complexity

3. Quadratic Complexity

4. Logarithmic Complexity

The correct answer is: Constant Complexity

An algorithm is defined as having constant complexity when its running time or space usage remains unchanged, no matter how much the input data varies in size. This is represented mathematically as O(1). For instance, if an algorithm directly accesses a specific element in an array using its index, the time taken to perform this operation does not depend on the number of elements in the array; it will always take the same amount of time. This is a prime example of constant complexity. In contrast, linear complexity indicates that the time taken increases linearly with the size of the input, while quadratic complexity suggests that the time increases based on the square of the size of the input. Logarithmic complexity, on the other hand, means the time grows logarithmically with input size, which is still dependent on how large the dataset gets. Therefore, the defining characteristic of constant complexity sets it apart from the other complexity types, making it the correct answer to the question.