Suppose we have a function that has a runtime which may be represented by the following equation:
T = mn - m^2 + m (where m and n are inputs to the function)
How would we analyze (worst-case) this runtime using big O notation if the variables were... a) independent? b) dependent such that m <= n for all valid inputs?
That is, how would we simplify the runtime equation using big O notation in each of these two scenarios?
a) I based my analysis around lecture notes that I found from Washington University. In short, if input variables are independent, then we must consider and retain the term(s) that dominate when m is large and when n is large respectively:
When m is large, the second term (-m^2) grows the fastest, and thus, we will preserve this term. When n is large, the first term (nm) grows the fastest, and thus, we will preserve this term. So, since there are no constants, O(nm-m^2).
b) On the contrary, I cannot find a resource that helps explain runtime analysis when variables are dependent (one would be greatly appreciated), so I rationalized it in the best way that I could....
As mentioned above, suppose m <= n for all valid inputs of the function. We will again consider our two cases:
When m is large, n is just as large or larger (given the relationship above). As a result, the value of nm will be greater than or equal to the absolute value of -m^2, meaning that nm dominates.
When n is large, m can take on any value less than or equal to n. As a result, nm will be greater than or equal to the absolute value of -m^2, meaning that nm dominates.
So, since there are no constants, O(nm).
My only gripe with this second Big O notation is that it is misleading. Moreover, it implies that the runtime for the given function is directly related to nm. So, as nm increases, the runtime should also increase.
Hypothetically, let's say n = 5 and m = 3.
If we used our original runtime equation, T = nm - m^2 + m = 5(3) - 3(3) + 3 = 9.
Now, let's say n = 5 and m = 5.
Based on our big O notation, since nm was equal to 15 and now it is equal to 25, there should be a corresponding increase in runtime. However, runtime actually decreases:
T = (5)(5) - (5)(5) + 3 = 3.
Are my analyses correct? If not, how would I go about it?
Bravo, your analysis is correct. In scenario (a), the dominant term is -m^2, when m is large, while when n is large it is nm. The big O notation of O(nm - m^2).
Regarding the second scenario, you correctly identified that (since m <= n) the dominant term is always nm, regardless of whether m or n is larger. Then the big O notation of O(nm).
The magnitude of n will always impact the total processing time, and therefore, it should be included in the time complexity analysis (as n increases, the processing time will increase too).
In the exceptional case in which m is equal to n, it is true that the runtime decreases even though nm increases.
However, it is not relevant in the overall time complexity analysis, since it does not affect the general behaviour of the function for most of the inputs.
This example demonstrates why the big O notation is an asymptotic upper bound, and not an exact representation of runtime. O(nm) is a bound on the worst-case runtime, but it doesn't tell us anything about the exact runtime for specific inputs.