'What has a larger big-O: O(m^2n) or O(n^2)
Given that m <= n, is O(n^2) in O(m^2n)? I know that O(mn) is in O(n^2) but I do not know what happens when you add the extra term
Solution 1:[1]
Even as m grows with n, and no matter the difference between m and n, n^2 will always be larger so (m^2)n would always be contained within n^2.
Solution 2:[2]
Given that m <= n, is O(n^2) in O((m^2)n)
No, even if m grows with n.
Let m = sqrt(sqrt(n)).
O(n^2) is not contained in O((m^2)n) = O(((sqrt(sqrt(n)))^2)n) = O(sqrt(n)n)
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Tario You |
| Solution 2 |