1
$\begingroup$

I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read examples in books because authors don't always give precision about whether the given result is a time or space complexity.

So, when you see that an algorithm has a O(n) complexity, you don't know much. You have to say: this algorithm has a O(n) time complexity.

IHMO I think it would be much more useful to use two separated letters like O(n) and T(1) for instance.

Is there such convention when talking about algorithm complexity?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Big O notation comes from number theory.

It's not about time or space at all. It's about the rate of growth of functions.

Even in computer science, we use it measure many other quantities, for example the number of rounds in a protocol, the depth of a circuit, the error probability of an algorithm, and so on.

Improve this answer
$\endgroup$

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.