Question

True or False...Provide your reasons

1. If f(n) =o(g(n)), then f(n)=O(g(n))
2. If f(n) =O(g(n)), then f(n) ≤ g(n)

3.  If 1<a=O(n^a), then f(n)=O(n^b)

4. A and B are two sorting algorithms. If A is O(n²) and B is O(n), then for an input of X integers, B can sort it faster than A.

Answer 1

Ans

False

f(n) = o(g(n)) does not imply f(n)= O(g(n))

It means f(n)<c.g(n) but does not mean f(n)<=c.g(n)

False

f(n) = O(g(n)) means f(n)<=c.g(n) where c>0 but it does not mean c=1. Hence f(n) <=g(n) is not inference .

3) False

1<a=O(n^{​​​​​​a}) means 1<a<=c.n^a

then f(n)<=c.n^b

^{we can't say anything about f(n) and b.}

4) True

B is O(n) while A is O(n²). So, number of operation in B less than that of A for n>0. So, B execute faster.

If any doubt ask in the comments.