Can't understand the $O$ notation for runtime of algorithms

Question

In my book,the $O$-notation is given as: $$O(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{>0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\leq \alpha g(n)\}$$
The algorithm(in pseudocode) for simple primality is given as:
input: $n\in \mathbb N$
output: $result$
main code:
if($n<2$)
result="no" else
for $i\rightarrow 2$ to $\lfloor {\sqrt n}\rfloor$ do
if($i|n$)
result="no"
output result
It says that if $g:n\rightarrow \sqrt n$ where $n\in \mathbb N $, and $f:\mathbb N\rightarrow R_{\geq 0}$ which counts the number of elementary operations of the above given algorithm.Then $f \in O(g)$. I justified this as
No matter what $f(n)\leq \lfloor \sqrt n \rfloor-1 < \lfloor \sqrt n \rfloor \leq g(n)$
and thus, we get the result.But then it states that

One can even say in this case that the algorithm has running time $\Theta(\sqrt n)$, because the number of steps performed by the algorithm is also never less than $\sqrt n$

which is opposite to what I just said.

Answer 1

You are looking at worst-case analysis in your book, i.e. how many steps does the algorithm perform in the worst-case. So the statement should at least be amended to say

One can even say in this case that the algorithm has running time $\Theta(\sqrt n)$, because the number of steps performed by the algorithm in worst-case is also never less than $\sqrt n$

This is still not a good explanation. Consider first that we can define $\Omega$ analogously to $O$ as:

$$\Omega(g)=\{f:\mathbb N\rightarrow \mathbb R_{\geq 0}:\exists \alpha\in \mathbb R_{\geq 0},\exists n_0 \in \mathbb N : \forall n\geq n_0 f(n)\geq \alpha g(n)\}$$

Note the change from $\leq$ to $\geq$. We know that $f \in \Theta(g)$ if and only if $f \in \Omega(g)$ and $f \in O(g)$.

You have already justified $f \in O(g)$. To justify $f \in \Omega(g)$ note that for example for $\alpha = 0.5, n_0 = 18$ we have $\lfloor \sqrt n \rfloor - 1 \geq \alpha g(n) = 0.5 \cdot \sqrt n$ for $\forall n \geq n_0$.

To see this holds consider that $\sqrt n - (\lfloor \sqrt n \rfloor - 1) < 2$ while $\sqrt n - 0.5 \cdot \sqrt n > 2$ for $\forall n \geq n_0$. Together this gives $2 + 0.5 \cdot \sqrt n < \sqrt n < 2 + (\lfloor \sqrt n \rfloor - 1)$, which finally yields $\lfloor \sqrt n \rfloor - 1 \geq 0.5 \cdot \sqrt n$.

Answer 2

As it come out from comments we are talking about book Stefan Hougardy, Jens Vygen - Algorithmic Mathematics-Springer International Publishing (2016), where algorithm in question is on page 8.

Confusing moment from page 10

" ..the number of steps performed by the algorithm is also never less than $\sqrt{n}$ "

can be explained from page 9

It is also not immediately clear whether computing the square root can be accomplished with an elementary operation; this can, however, easily be avoided by increasing i stepwise by 1 until $i \cdot i \gt n$.

Last sentence shows, the number of steps considered by the authors satisfies the condition $i \gt \sqrt{n}$.