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

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.

• Does it really say "is also never less than n"? Or does it say $\sqrt n$? Saying $f \in \Theta(g)$ is the same as saying both $f \in \Omega(g)$ and $f \in O(g)$. Does that help you? Jul 26 at 9:55
• It says that number of steps performed is never less than $\sqrt n$ Jul 26 at 9:59
• I cant understand that Jul 26 at 10:00
• The quoted sentence talks about $\Theta(\sqrt{n})$, which is different from $O(\sqrt{n})$. Jul 26 at 10:02
• but $f(n)<\sqrt n$.I am confused. Jul 26 at 10:05

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

• But the worst case is when $f(n)=\lfloor {\sqrt n} \rfloor-1$ which is always less than $\sqrt n$ Jul 26 at 10:56
• @queen_of_fat_blobs Constants never matter in Landau notation. If $h(x) \in O(g)$ or $h(x) \in \Omega(g)$ or $h(x) \in \Theta(g)$ so is $h(x) + k$ for any $k \in \mathbb{R}$. Nevertheless, I've updated my answer to show that you can indeed always find suitable $n_0$ and $\alpha$ rather easily. Jul 26 at 11:34

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

• thankyou for proper clarification. Jul 27 at 18:00
• Glad to be useful. Jul 27 at 18:40