1.
MathWorks technical mcq question, verified with a worked answer. Free to practise - no sign-up.
1. (Math Question) Complexity
If f(n) = O(n) and g(n) = O(n), what is the upper bound for (f+g)(n)?
Pick ONE option
Show answer & explanation
When adding two functions with the same asymptotic complexity, the result is dominated by that complexity. Since f(n) = O(n) and g(n) = O(n), the sum (f+g)(n) = O(n) + O(n) = O(n). Big-O complexity addition follows the rule that O(c·g(n)) = O(g(n)) for constant c, so O(n) + O(n) = O(2n) = O(n).
Step-by-step Derivation:
By definition, if f(n) = O(n), then ∃ constants c₁, n₁ such that f(n) ≤ c₁·n for all n > n₁. Similarly, g(n) = O(n) means ∃ constants c₂, n₂ such that g(n) ≤ c₂·n for all n > n₂. Therefore, (f+g)(n) = f(n) + g(n) ≤ c₁·n + c₂·n = (c₁ + c₂)·n for all n > max(n₁, n₂). Since (c₁ + c₂) is a constant, (f+g)(n) = O(n). The other options represent unnecessarily loose upper bounds: O(n²), O(n³), and O(n!) are all valid but not tight bounds.