Menu
This is a basic question... but I'm thinking that O(M+N) is the same as O(max(M,N)), since the larger term should dominate as we go to infinity? Also, that would be different from O(min(M,N)), is that right? I keep seeing this notation, esp. when discussing graph algorithms. For example, you routinely see: O(|V| + |E|) (e.g., http://algs4.cs.princeton.edu/41undirected/).
610
O(mn) for a m x n matrix means that you're doing constant work for each value of the matrix. O(n^2) means that, for each column, you're doing work that is O(# columns). Note this runtime increases trivially with # of rows.
The time needed to complete the operation is proportional to the square of the arrays's length. Note: If both array have the same size, the time complexity is O(N^2) If both array have a different size, the time complexity is O(N.M) (as in N times M, where N and M are the array sizes)
To sum up: O(mn) is generally called linear for things like matrix multiplication because it's linear in the size of the input, but it's generally called quadratic for things like string matching because of the smaller input.
O(n) means that the time/space scales 1:1 with changes to the size of n. If a new operation or iteration is needed every time n increases by 1, then the algorithm will run in O(n) time. The previous example ofO(1) space complexity runs in O(n) time complexity.
Yes, O(M+N) means the same thing as O(max(M, N)). That is different than O(min(M, N)). As @Dr_Asik says, O(M+N) is technically linear O(N) but when M and N have a meaning, it is nice to be able to say "linear in what?" Imagine the algorithm is linear in the number of rows and the number of columns. We can either define N = rows + cols and say O(N) or we can say O(M+N) where M is rows and N is columns.
178
Linear time is noted O(N). Since (M+N) is a linear function, it should simply be noted O(N) as well. Likewise there is no sense in comparing O(1) to O(2), O(10) etc., they're all constant time and should all be noted O(1).
43
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
