Peter Linz, 3rd Ed, Chapter 1, Pg 15, Ques 19

Question

if f(n) = O(n²) and g(n) = O(n³), then

what is the complexity of f(n)*g(n) and f(n)/g(n) in big-o-notation?

Answer 1

Given f(n)=O(n$^{2}$) and g(n)=O(n$^{3}$)

Hence as per definition,

f(n)<=c*n$^{2}$, f(n) can be n$^{2}$, n$^{2}$/logn, nlogn,n,constant,1/n,1/n$^{2}$,1/2$^{n}$,...

Similarly,

g(n)<=c*n$^{3}$, f(n) can be n$^{3}$, n$^{2}$, nlogn,n,constant,1/n,1/n$^{2}$,1/2$^{n}$,...

Solution:

[I] f(n)*g(n) <= [constant *largest possibile eqn in f(n) ]*[constant *largest possibile eqn in g(n) ]=constant*n$^{2}$*constant*n$^{3}$

i.e. f(n)*g(n)<=c*n$^{5}$,

Hence f(n)*g(n)=O(n$^{5}$).

[II] f(n)/g(n) <= [constant *largest possibile eqn in f(n) ] / [constant *smallest eqn in g(n) ]

Since the lowest equation is not bounded for g(n), it can be 1/n, 1/n!,1/2$^{n}$,1/n$^{n}$, and even lower than that

Hence f(n)/g(n) does not have an upper bound. 

Answer 2

 f(n) = O(n²)

 g(n) = O(n³)

 f(n) * g(n) = O(n^2)  * O(n^3) = O(n^5)

f(n) / g(n)  = O(n^2) /  O(n^3) = O(1/n)

Comments

The book says that f(n)*g(n) = O(n^6). (I think it might be an error but need clarification).

And in case of division, I think it should be O(n^2) because we need to take the maximum of numerator and minimum of denominator so as to get the worst case.

Please someone verify.

---

why f(n) * g(n) = O(n^2)  * O(n^3) = O(n^5) and f(n) / g(n)  = O(n^2) /  O(n^3) = O(1/n) ?

We are basically calculating f(n) and g(n) and then doing one operation (multiplication or division).

Calculating f(n) will take O(n²)  and calculating g(n) will take O(n³) . Then mult or div will take constant time O(1).

So,

f(n) * g(n) = O(n^2)  + O(n^3) + O(1) = O(n^3)

f(n) / g(n) = O(n^2)  + O(n^3) + O(1) = O(n^3)

---

big O means maximum possible means worst case possible in the case of multiplication worst case should be possible o(n^5). but in the case of division it should be O(n^3) why because for worst case (f(n)/g(n)) f(n) should be maximum and g(n) should be minimum given that f(n)=O(N^3) so maximum is n^3 and g(n)=O(n^2)[value possible 1 to n^2] for minimum  we have to take g(n)=1 then in this case f(n)/g(n)=O(n^3).