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?
Asked By : Robert Hönig
Answered By : Yuval Filmus
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.
Question Source : http://cs.stackexchange.com/questions/65933
0 comments:
Post a Comment
Let us know your responses and feedback