1
  1. Suppose (without code) we have a function that takes two inputs n and k. Assume that there is no relationship between these two variables. Let's say that we can simplify the Big O time complexity to O(n/k + n + k). From here, would we be able to achieve a tighter bound? My thinking is as follows:

    When handling analysis with multiple unrelated inputs, it is best to consider which term is dominant when each variable is very large. When k is very large, the k term is dominant over the n/k term. Moreover, as we approach very large numbers of k, the k term will approach positive infinity while the n/k term will approach 0. Additionally, when n is very large, the n and n/k terms "tie". That is, both values will approach infinity at relatively comparable rates. Since the n/k term is not the dominant term for either variable, it would seem logical to remove it from our expression. So, our bound would be O(n + k). Is this correct?

  1. As an extension, suppose we have a function that takes a single input of n. Let's say that we can simplify the Big O time complexity to O(1/n). Based on the logic I applied above, as we approach very large numbers, the 1/n term approaches 0. In this way, a constant of an arbitrary value, which does not contain an n, would dominate the 1/n term. So, would it be fair to simplify the time complexity of this algorithm to O(1)?
LateGameLank
  • 113
  • 5
  • 1
    I think you are correct in your thinking. *O(1/n)* is a little philosophical; see e.g. this question: https://stackoverflow.com/questions/905551/are-there-any-o1-n-algorithms – Berthur Aug 07 '23 at 13:01

0 Answers0