Is it true that $\dfrac{n}{2\sqrt{n}-1}=\Theta(\sqrt{n})$?

Question

I have a function of the form

$$f(n)=\dfrac{n}{2\sqrt{n}-1}.$$

I would like to find the big-O of this function (or big-Theta). How can I find these?

I tried this method: Multiply both the denominator and the numerator by $\sqrt{n}$. I get:

$$f(n)=\dfrac{n\sqrt{n}}{2n-\sqrt{n}}.$$ Now, as $n$ goes large, we get $f(n)=\sqrt{n}/2$. Can I say that $f(n)=\Theta(\sqrt{n})$?

For large $n$, we have $$\frac{n}{2\sqrt{n}-1}\le\frac{n}{2\sqrt{n}}=\frac{\sqrt{n}}{2}.$$ — Adrian Keister, May 15 '18 at 15:06

score 1 · Accepted Answer · answered May 15 '18 at 15:05

1

Recall the definition and note that for $n\to \infty$

$$\frac{\dfrac{n}{2\sqrt{n}-1}}{\sqrt n}=\dfrac{n}{2n-\sqrt{n}}\to \frac 12$$

answered May 15 '18 at 15:05

user

154,566

This proves that $f(n)=O(\sqrt{n})$. Can we prove the lower bound, i.e., $f(n)=\Omega(\sqrt{n})$? – zdm May 15 '18 at 15:26
Why? This proves $f(n)=\Theta(\sqrt{n})$, because the limit is a non-zero constant. – poyea May 15 '18 at 15:34
1

@zdm By definition of limit we have that eventually $$k_1 \sqrt n\le f(n) \le k_2 \sqrt n$$ – user May 15 '18 at 15:38

score 1 · Answer 2 · answered May 15 '18 at 16:52

If you make the denominator bigger, that makes the fraction smaller, and vice versa. We can get both inequalities for $\Theta(\sqrt{n})$, though: $$\sqrt{n}=\dfrac{n}{\sqrt{n}}=\dfrac{n}{2\sqrt{n}-\sqrt{n}}\ge\dfrac{n}{2\sqrt{n}-1}\ge \dfrac{n}{2\sqrt{n}}=\dfrac{\sqrt{n}}{2}.$$ Therefore, $f(n)=\Theta(\sqrt{n})$.

Is it true that $\dfrac{n}{2\sqrt{n}-1}=\Theta(\sqrt{n})$?

2 Answers2