World's most popular travel blog for travel bloggers.

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

, , No Comments
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 :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback