Suppose (without code) we have a function that takes two inputs
nandk. Assume that there is no relationship between these two variables. Let's say that we can simplify the Big O time complexity toO(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
kis very large, thekterm is dominant over then/kterm. Moreover, as we approach very large numbers of k, thekterm will approach positive infinity while then/kterm will approach0. Additionally, whennis very large, thenandn/kterms "tie". That is, both values will approach infinity at relatively comparable rates. Since then/kterm is not the dominant term for either variable, it would seem logical to remove it from our expression. So, our bound would beO(n + k). Is this correct?
- 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 toO(1/n). Based on the logic I applied above, as we approach very large numbers, the1/nterm approaches0. In this way, a constant of an arbitrary value, which does not contain ann, would dominate the1/nterm. So, would it be fair to simplify the time complexity of this algorithm toO(1)?