-1

$$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.

epimorphic
  • 3,219
stanley cho
  • 99

2 Answers2

2

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

Bernard
  • 175,478
  • 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. – Zubin Mukerjee Jun 04 '17 at 22:06
  • @ZubinMukerjee: I would even say they grow infinitely faster, to use a striking phrase. – Bernard Jun 04 '17 at 22:41
  • @Bernard. Welcome to the club of victims of mysterious downvotes ! – Claude Leibovici Jun 05 '17 at 05:13
2

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)$.

JoseA132
  • 528
  • 2
  • 12