Amazon Interview Question Software Development Managers
Country: India
If O is function, then answer is (2), if O is constant, then answer is (4)
if f(n) = O(g(n)) = g(n)^2 Note: O(x) = x^2
then 2f(n) = 2O(g(n)) = 2g(n)^2
using this O function, if g(n) = 3, then f(n) = O(3) = 3^2 = 9
2f(n) = 18, O(2g(n)) = O(2x3) = O(6) = 6^2 = 36.
So, 2f(n) <= O(2g(n)).
But if O function = SQRT(x), then:
if g(n) = 3, then f(n) = O(3) = SQRT(3)
2f(n) = 2*SQRT(3), O(2g(n)) = SQRT(2x3) = SQRT(6)
in this case, 2f(n) > O(2xg(n))
So, I think answer is (2)
Is 2f(n)=O(2g(n))? effectively implies is 2f(n)=O(g(n))? Because, in Big-Oh notation, we drop the leading constants.
To answer "is 2f(n)=O(g(n))?", we have:
f(n)=O(g(n)), which means
f(n) <= Cg(n), for some C>0 & for all n >n0
Multiply by 2 on both the sides
2f(n) <= 2Cg(n). Now let D= 2C
2f(n) <=Dg(n), which implies
2f(n) = O(g(n))
Hence 4(Always) is the answer. Since 4(Always) is the answer, 1(Never) and 2(Sometimes) are NOT the answers. 3(Yes if f(n)≤g(n) for all sufficiently large n) is an implication of the assertion "f(n)=O(g(n))" provided in the question. Therefore, it is a part of the question and is not an answer.
Answer is (4), Always.
- Aniket March 19, 2012I.e. IF f(n) = O(g(n)) ie. C*g(n) is an upper bound on f(n), where C is a constant,
2 f(n) = O(2g(n)) as 2g(n) WILL always be an upper bound on 2 f(n).