## 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).