Can I notate time complexity depending on the result of an algorithm?

Problem Detail: 

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65933

3200 people like this

 Download Related Notes/Documents