I have a program that calculates the first year some two events happen on the same day. I have not calculated any upper limit for the year. The time complexity of the program would be equivalent to O(Years), where Years is the result of the algorithm.

Is such a notation possible?

If yes, can I call the algorithm "linear"?

If not, what would be the correct way of notating the complexity?


You can use whatever notation you want, as long as you explain what it means.

A linear time algorithm usually means an algorithm running in time $O(n)$, where $n$ is the length of the inputs in bits or in machine words (depending on the computation model). The only exception is algorithm which produce a large amount of output. In that case you can say that the algorithm runs in time linear in the output length.

  • $\begingroup$ So my algorithm wouldnt be linear. But what would it be then? $\endgroup$ – Robert Hönig Nov 12 '16 at 16:32
  • $\begingroup$ Without more information, it is impossible to say. It could even be linear time. By running time we usually mean "worst-case running time as a function of input length". $\endgroup$ – Yuval Filmus Nov 12 '16 at 16:35
  • $\begingroup$ You would say your algorithm is linear in the value of the result "Year". Just "linear" is understood to mean "linear in the length of the input", but if you state explicitly what it is linear in, that's fine. $\endgroup$ – gnasher729 Nov 12 '16 at 22:02

You can express algorithms costs in whichever parameters you desire, so long as you define them. The parameters don't even have to be known given the input; that gives your bound limited use, but well.

Warning: Landau bounds are asymptotic, that is they only hold meaning when you let the parameter(s) go towards infinity. That is you can not really use parameters that can not be arbitrarily large.

Warning: It's unlikely that your cost is independent of the input, which is what your bounds seems to suggest. You probably made a mistake.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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