Rosen ch.3

Question

Q.1 :Give a big-O estimate for f(n)=3n log(n!) + ($n^2$+3)log n, where n is positive integer

Answer is given as O($n^2$ logn), Why it is not O($n^3$)?

Q.2: Find the least integer n such that f(x) is O($x^n$)

f(x)=2$x^2$ + $x^3$logx

here n is given as 4, why it can not be 3??

Comments

For the first part :-

$f(n)=3nlog(n!)+(n^{2}+3)log(n)$.

We know that ,

$log(n!) = \Theta(nlogn)$.

Now , $f(n)=\Theta(n^{2}log(n))+\Theta(n^{2}log(n))+\Theta(log(n))$.

Lower order terms don't affect the asymptotic complexity.

$f(n)=\Theta(n^{2}log(n))$.

Thus $f(n)$ can be writtern as $O(n^{2}log(n))$.

You can say it as $O(n^{3})$ , but $O(n^{2}log(n))$ is tighter.

Answer 1

Ans1) I am not getting $O(n^{3})$ but let me walk you through my approach to this problem.

$3nlog(n!)=3n*\left \{ log(n*(n-1)*(n-2)*..........*2*1) \right \}\\=>3n*\left \{ log(n)+log(n-1).......log(2)+log(1)\right \}\\=>log(n)^{3n}+log(n-1)^{3n}+.....+log(2)^{3n}+0^{3n}\\=>O(3n*log(n))\\\\(n^{2}+3)*log(n)=n^{2}*log(n) + 3log(n)=O(n^{2}log(n))\\\\ \therefore O(3n*log(n))+O(n^{2}log(n))=O(n^{2}log(n))$

Ans 2)  n should be greater than 3 ,for if it's 3,$O(x^{3})<O(x^{3}*log(x))$ but if n=4, $O(x^{4})>O(x^{3}*log(x))$,and so $O(f(x))=O(x^{4})$

Comments

@Debdeep1998 @prashant jha 1

Ok I got my mistake in the 2nd part

but in the 1st part ,the method given in rosen is breaking the functions use this theorem: Suppose that f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then (f1.f2)(x) is O(g1(x)g2(x))

Now  f(n)=3n log(n!) + (n^2 log n) + 3log n

3n log(n!) is O(n^2 logn)

n^2 log n is O(n^3)

3log n is O(n)

overall it should be O(n^3)...what is wrong in this?

---

nothing wrong with it.. Here, $f(n) \in O(n^{2}lgn)$ and $f(n) \in O(n^{3})$ both are correct. when we write $f(n) \in O(g(n))$, It means function $f(n)$ belongs to set of functions $g(n)$ for which $f(n) \leq cg(n)$ for some $c>0$. So, suppose, if $f(n)$ belongs to $g(n)=c*n$ , where $c>0$ then it will also belong to those functions which are upper bounded by $c*n$ because if we can find atleast one $c>0$ for $f(n) \leq cg(n)$ then we will definitely find atleast one $c$ for those functions which are upper bounded by $g(n)$

---

@ankitgupta.1729 I got your point, but how to decide which is the tightest upper bound here

I think I have done a mistake, for $n^2$log n,it should be O(n^2log n) only (for tighter upper bound) not O(n^3)...Right??

---

@himgta big oh 'O' is used for asymptotic upper bounds not asymptotic tight upper bounds. We use small 'o' for functions which are not asymptotic tight upper bounds.  

So , here I have to show $g(n) = n^3$is not asymptotic tight upper bound.

So, to show something is not asymptotic upper bound , we have to use definition of small 'o' notation.

Definition of $f(n) = o(g(n))$ says $f(n) \leq cg(n)$ for all $c>0$ and $n \geq n_{0}$ . Here difference b/w big O and small o is that small o is used for all $c>0$ and big O is used for some $c>0$

So, here we have to know 3n log(n!) + (n^2+3)log n $ \leq cn^3$ is true or not for all $c>0$ or not.

In other way we can write $f(n) = o(g(n))$ as $\lim_{n\rightarrow \infty }\frac{f(n)}{g(n)} = 0$

So, overall if we prove $\lim_{n\rightarrow \infty }\frac{3nlogn! + n^{2}logn +3logn }{n^{3}} = 0$ then we say that it is not a tight upper bound.

here, for n! , use stirling's approximation and use L-Hospitals's rule here, then it will give 0 , so it will be not be tight upper bound. So, remaining function $n^2logn$ will be tight upper bound.These things are given in cormen. So, you can verify it.