0

  1. Are there any algorithms that do not have time complexities that are strictly increasing? (Excluding constant time complexities)

  2. Do all strictly increasing functions with the same big theta class have derivatives which grow at rates that are constant multiples of each other?

  3. Finally, if the above assertions are true, does this mean that all practical time complexities are in the same big theta class if their derivates are constant multiples of each other?

If we restrict our analysis to only strictly increasing functions, and if algorithms are only ever described by strictly increasing functions, is big theta analysis essentially just comparing derivatives/growth rates?

I have seen posts talking about how Big theta is not necessarily the same as looking at the derivates of a function: https://math.stackexchange.com/questions/221720/big-o-notation-basics-is-it-related-to-derivatives

alephnull14177
  • 1
  • Since this site's objective is to answer specific technical questions and not to provide tutorial services. I suggest you avail yourself of the numerous resources on the web to assist one in determining the time complexity of an algorithms and/or code. [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) is a good starting point. – itprorh66 Jun 13 '23 at 20:24
  • (1) Yes. Computing ta length of a Collatz period for a given number is extremely fast for powers of 2, and could be indefinitely long for some other numbers. – user58697 Jun 14 '23 at 02:58
  • @itprorh66 I am well versed in calculating time complexities. I'm asking some questions regarding big O in a rigorous mathematical context, and also applying it to the real world. I usually explain big O to others as a measure of growth rate, however that is not how people define it and with [good reason](https://math.stackexchange.com/questions/221720/big-o-notation-basics-is-it-related-to-derivatives). I'm asking if in certain circumstances big O is the same as comparing derivatives. – alephnull14177 Jun 24 '23 at 00:19
  • If you are stressing the mathematical computational aspects, the question should be directed to another Stackexchange site such as [Mathmatics](https://math.stackexchange.com/) – itprorh66 Jun 24 '23 at 15:11
  • Alrighty. I wasn't sure where to ask this because I was also asking application related questions – alephnull14177 Jun 25 '23 at 22:36

0 Answers0