-2
$\begingroup$

$$r(n) = \Big(\sqrt{n}+20\log_2(n)+n/2\Big)\big(4n+\log(n)+5\big)$$

This was part of my computing science quiz, and I still can't happen to understand how to find the simplest big O estimate. It would be greatly appreciated if someone could help me find the answer to this.

$\endgroup$

closed as off-topic by Namaste, Claude Leibovici, user91500, Arnaldo, John B Jun 5 '17 at 13:31

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Claude Leibovici, user91500, Arnaldo, John B
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I've edited your equation (this site uses MathJax for LaTeX typestting of expresssions). $\endgroup$ – Zubin Mukerjee Jun 4 '17 at 22:02
  • $\begingroup$ Oh yes!! My mistake... Thank you!! :) $\endgroup$ – stanley cho Jun 4 '17 at 22:03
2
$\begingroup$

I assume this is Big O for programming so $n\in\mathbb{N}$.

$r(n)=\left(\sqrt{n}+20\log_2(n)+\frac{n}{2}\right)(4n+\log(n)+5)$
$\Longrightarrow r(n)=4n\sqrt{n}+\log(n)\sqrt{n}+5\sqrt{n}+80n\log_2(n)+20\log(n)\log_2(n)+100\log_2(n)+2n^2+\frac{n}{2}\log(n)+\frac{5n}{2}$

Since $\exists c\in\mathbb{N}$ such that $\exists N_0\in\mathbb{N}$ and $\forall n\in\mathbb{N},~n\ge N_0,~r(n)\le c\cdot n^2\Longrightarrow r(n)\in O(n^2)$.

Prove:
$\begin{array}{rclc} 4n\sqrt{n} & \le & 4n^2 & (n\ge1)\\ \log(n)\sqrt{n} & \le & n^2 & (n\ge1)\\ 5+\sqrt{n} & \le & 6n^2 & (n\ge1)\\ 80n\log_2(n) & \le & 80n^2 & (n\ge1)\\ 20\log(n)\log_2(n) & \le & 20n^2 & (n\ge1)\\ 100\log_2(n) & \le & 100n^2 & (n\ge1)\\ 2n^2 & \le & 2n^2 & (n\ge1)\\ \frac{n}{2}\log(n) & \le & n^2 & (n\ge1)\\ \frac{5n}{2} & \le & 3n^2 & (n\ge1)\\ \Longrightarrow r(n) & \le & 217n^2 & (n\ge1) \end{array}$

So we can choose $c=217$ and $N_0=1$.

Also, $r(n)\in\Omega(n^2)$, since all functions in the sum are positive for $n\ge1$ then for $c=1$ and $N_0=1$ we have this trivial affirmation: $\forall n\in\mathbb{N}:n\ge N_0: c\cdot n^2\le r(n)$.

So $r(n)\in\theta(n^2)$ because $r(n)\in\Omega(n^2)~\wedge~r(n)\in O(n^2)$.

$\endgroup$
  • $\begingroup$ @TMM What's LHS and RHS? $\endgroup$ – JoseA132 Jun 4 '17 at 23:31
  • $\begingroup$ Left/right hand side. $\endgroup$ – TMM Jun 5 '17 at 0:24
1
$\begingroup$

We know $\log n=o(\sqrt n)$, $\sqrt n=o(n)$ hence both factors are $O(n)$, and their product is $O(n^2)$.

$\endgroup$
  • $\begingroup$ Good answer! +1 ... to add some intuition: $n/2$ grows faster than either of $\sqrt{n}$ or $20\log_2(n)$, so the term $n/2$ determines the growth rate of the first factor. Likewise $4n$ determines the growth rate of the second factor. $\endgroup$ – Zubin Mukerjee Jun 4 '17 at 22:06
  • $\begingroup$ @ZubinMukerjee: I would even say they grow infinitely faster, to use a striking phrase. $\endgroup$ – Bernard Jun 4 '17 at 22:41
  • $\begingroup$ The compulsive downvoter struck again, apparently. May I have the honour to know why this downvote? $\endgroup$ – Bernard Jun 4 '17 at 22:51
  • $\begingroup$ @Bernard. Welcome to the club of victims of mysterious downvotes ! $\endgroup$ – Claude Leibovici Jun 5 '17 at 5:13

Not the answer you're looking for? Browse other questions tagged or ask your own question.