1

In computer science, algorithms are often characterized by their computational complexity — for example, a primitive sorting algorithm’s complexity may be O(n2) where n is the size of the input list. Similarly, in physics, one might say that one quantity changes with the square of another without getting into all details of the formula if they are not relevant at the moment.

I’m looking for a more elegant way of expressing the type of function and the fact that the quantity that execution time depends on is the size of the input list rather than something else. For linear complexity, O(n), one could say that execution time is proportional to the size of input.

Is it correct to say that execution time is linear/logarithmic/square in the number of input elements (or the number of bytes, or another quantity)? Should I use in, or another preposition or perhaps some completely different grammatical construction to express this kind of dependency?

1 Answer 1

3

Here are three standard ways.

  • execution time varies [linearly with/logarithmically with/as the square of] the number of input elements

  • execution time depends [linearly/logarithmically/quadratically] on the number of input elements

  • execution time is a [linear/logarithmic/quadratic] function of the number of input elements

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.