Algorithm complexity: Proof that $\lfloor\sqrt{n}\rfloor \geq \frac{\sqrt{n}}{2}$ and $n-\lfloor\sqrt{n}\rfloor+1\geq \frac{n}{2}$, $\forall n\geq 2$

Question

Background / Context:

I'm currently calculating the complexity of the following algorithm:

for j = 1 to n
    if j*j <= n
       for k = j to n
           f()

The function call f() is $\Theta(1)$. Through my research, with the following inequalities I can define the bounds for operation calls. The exercise is rather trivial, so I was rather interested in formally proving said inequalities and exploring a more general case:

Given $n\geq 2$:

1. $\lfloor\sqrt{n}\rfloor \geq \frac{\sqrt{n}}{2}$
2. $n-\lfloor\sqrt{n}\rfloor+1\geq \frac{n}{2}$

Besides the proofs for these, they seem to be like there could be an intuitive explaination for me to grasp this better.

Also, is there a generalization of these statements for example changing the divisions by $2$ to divisions by $k$, $\sqrt{n}$ to $\sqrt[k]{n}$ and valid for $n\geq k$?

Answer 1

Thank you to @Gary for a proof of statement 1. As for 2, it suffices to prove the stronger inequality: $$n-\sqrt{n}+1\geq n/2$$ Proof of 2: Start with: $$(\sqrt{n}-1)^2+1\geq 0$$ $$n-2\sqrt{n}+2\geq 0$$ $$\frac{n}2-\sqrt{n}+1\geq 0$$ $$n-\sqrt{n}+1\geq \frac n2$$ Proven as required.

Now consider the general case of the first statement: $$\lfloor n^{1/k} \rfloor \geq \frac{n^{1/k} }{k}$$ Proof of general case of 1: It is possible to prove the more general case: $$\lfloor n^{1/k} \rfloor \geq n^{1/k}-1 \geq \frac{n^{1/k} }{k}$$ $$n^{1/k}(k-1) \geq k$$ Now the general idea is to somehow use the definition of $e$ to help us. First of all we have to use $n>e>(1-1/k)^{-k}$ when $n\geq 3$, and then treat $n=2$ as a separate case: $$n^{1/k}(k-1) \geq k$$ $$n^{1/k} \geq (1-1/k)^{-1}$$ $$n \geq (1-1/k)^{-k}$$ Now since $n\geq3>e>(1-1/k)^{-k}$, the $n\geq 3$ case is proven as required. As for the $n=2$ case, we have: $$\lfloor 2^{1/k}\rfloor = 1 \geq 2/3\geq 2^{1/k}/3\geq 2^{1/k}/k$$ Also proven as required, and so we are done.

And finally, the general case of 2: $$n-\lfloor n^{\frac{1}{k}}\rfloor+1\geq n/k$$ Proof of general case of 2: We prove the stronger inequality $$n-n^{\frac{1}{k}}+1\geq n/k$$ $$(1-1/k)n+1\geq n^{\frac{1}{k}}$$ $$(1-1/k)n+1\geq n^{\frac{1}{k}}$$ Once again, we want to somehow use the definition of $e>(1-1/k)^{-k}$: $$n^k\geq ne$$ Since $n\geq 3$ and $k \geq 2$. And so: $$n^k\geq n(1-1/k)^{-k}$$ $$n\geq n^{1/k}(1-1/k)^{-1}$$ $$n(1-1/k)\geq n^{1/k}$$ $$n(1-1/k)+1 \geq n(1-1/k)\geq n^{1/k}$$ And so, proven as required, note that I had to handle the case $n=2$ separately as the above proof only does it for $n\geq 3$, which is why I had the proof at the start.