2

I want to prove the following$$n - 2\sqrt{n} = \Theta(n)$$

Is it correct to say $$n -1 \leq n \leq n +1 => f(n)=n=\Theta(n)$$ $$\sqrt{n}\leq|-2\sqrt{n}| = 2\sqrt{n}\leq3\sqrt{n} =>g(n)=-2\sqrt{n}=O\sqrt{n}$$

So:     $n - 2\sqrt{n} = max(O(n),O(\sqrt{n}))=O(n)$
And:  $n - 2\sqrt{n} = max(\Omega(n),\Omega(\sqrt{n}))=\Omega(n)$
So:     $n - 2\sqrt{n} = \Theta(n)$




Edit for possible duplicate:I am not interested in the solution to this problem , but whether my methodology for solving the problem is correct or not.

user248445
  • 53

1 Answers1

3

Three things:

1) I would use $\frac{1}{2}n\leq n\leq 2n$ to prove that $n=\Theta(n)$ (not $n+1$ and $n-1$ because we normally define big-O notation in terms of multiplicative constants).

2) It is true that $O(f-g)=\max\{O(f),O(g)\}$ because the growth rate of the difference is (at most) the growth rate of the largest one.

3) It is not true that $\Omega(f-g)=\max\{\Omega(f),\Omega(g)\}$ because of cancellation. Suppose that $f$ and $g$ are identical, then $\Omega(f-g)=\Omega(0)\not=\max\{\Omega(f),\Omega(g)\}$. This also shows that $\Omega(f-g)\not=\min\{\Omega(f),\Omega(g)\}$.

Michael Burr
  • 32,867