Suppose we have the function below:
def foo(n, k):
for _ in range(n-k):
for _ in range(n):
print("bar")
If I were to compute the time complexity of this function, I would say that the outer loop will iterates n-k times while the inner loop will iterate n times for each outer loop iteration. As a result, our print statement, which is O(1) runtime, will be executed n(n-k) times. Simplified, this number would be n^2 - nk times. My question is, then, how do we simplify this expression using big O notation?
I understand that one of the rules of Big O is to eliminate non-dominant terms. In this case, is -nk considered non-dominant, since the inputs n and k will always be non-negative, meaning that the term will always be a negative value? If we believed this to be true, then our simplified Big O would be O(n^2).
However, in cases where there are numerous variables, another rule is to preserve the dominant term for each variable. In this case, the only term containing k is the -nk term. Therefore, we would preserve this term. If we believed this to be true, then our simplified Big O would be O(n^2 - nk).
Thoughts?
>Solution :
No, you cannot just drop -nk because n^2 is not necessarily dominant.
n and k are just two variables. If you know something about them, or their dependence on each other, then and only then can you start making such simplifications.
Perhaps the source of your confusion: If the expression had been n^2 – n, then you could indeed drop the n term (regardless of its sign) because you know that n^2 is dominant.