Interview questions

Question

This is an interview question:

Given: f(n) = O(n)
       g(n) = O(n²)
find f(n) + g(n) and f(n)⋅g(n)?

What would be the answer for this question?

Answer 1

O(f(n) + g(n)) = O(max{f(n), g(n)}) 

so for first

f(n) + g(n) = O(max{n, n^2}) = O(n^2)

for

f(n) ⋅ g(n) 

we will have

O(f(n) ⋅ g(n)) = O(n ⋅ n^2) = O(n^3)

Answer 2

This question can be understood like this :-

f(n)=O(n) means it takes O(n) time to compute f(n).

Similarly,

for g(n) which requires O(n^2) time

So,

P(n)=f(n)+g(n) would definitely take O(n)+O(n^2)+O(1)(for addition, once you know the value of both f and g)

. Hence, this new function

P(n) would require O(n^2) time.

Same is the case for

Q(n) =f(n)*g(n) which requires O(n^2) time

.

Answer 3

Think about it this way.

f(n) = c.n + d
g(n) = a.n^2 + b.n + p

Then,
f(n) + g(n) = a.n^2 + (lower powers of n)
And,
f(n).g(n) = x.n^3 + (lower powers of n)

It follows that O(f(n) + g(n)) = O(n^2)

and O(f(n).g(n)) = O(n^3)

Answer 4

When this answer was prepared, f(n) was shown as o(n) and g(n) as Θ(n²).

From f(n) = o(n) and g(n) = Θ(n²) you get a lower bound of o(n²) for f(n) + g(n), but you don't get an upper bound on f(n) + g(n) because no upper bound was given on f(n). [Note, in above, Θ is a big-θ, or big theta]

For f(n)·g(n), you get a lower bound of o(n³) because Θ(n²) implies lower and upper bounds of o(n²) and O(n²) for g(n). Again, no upper bound on f(n)·g(n) is available, because f(n) can be arbitrarily large; for f(n), we only have an o(n) lower bound.

With the question modified to give only upper bounds on f and g, as f(n) = O(n) and g(n) = O(n²), we have that f(n)+g(n) is O(n²) and f(n)·g(n) is O(n³).

To show this rigorously is a bit tedious, but is quite straightforward. Eg, for the f(n)·g(n) case, suppose that by the definitions of O(n) and O(n²) we are given C, X, K, Y such that n>X ⇒ C·n > f(n) and n>Y ⇒ K·n² > g(n). Let J=C·K and Z=max(X,Y). Then n>Z ⇒ J·n³ > f(n)·g(n) which proves that f(n)·g(n) is O(n³).