Suppose (without code) we have a function that takes two inputs
n
andk
. 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
k
is very large, thek
term is dominant over then/k
term. Moreover, as we approach very large numbers of k, thek
term will approach positive infinity while then/k
term will approach0
. Additionally, whenn
is very large, then
andn/k
terms "tie". That is, both values will approach infinity at relatively comparable rates. Since then/k
term 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/n
term approaches0
. In this way, a constant of an arbitrary value, which does not contain ann
, would dominate the1/n
term. So, would it be fair to simplify the time complexity of this algorithm toO(1)
?