0
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ 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? $\endgroup$
    – idmean
    Jul 26 at 9:55
  • 1
    $\begingroup$ It says that number of steps performed is never less than $\sqrt n$ $\endgroup$ Jul 26 at 9:59
  • $\begingroup$ I cant understand that $\endgroup$ Jul 26 at 10:00
  • 1
    $\begingroup$ The quoted sentence talks about $\Theta(\sqrt{n})$, which is different from $O(\sqrt{n})$. $\endgroup$ Jul 26 at 10:02
  • $\begingroup$ but $f(n)<\sqrt n$.I am confused. $\endgroup$ Jul 26 at 10:05
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ But the worst case is when $f(n)=\lfloor {\sqrt n} \rfloor-1$ which is always less than $\sqrt n$ $\endgroup$ Jul 26 at 10:56
  • $\begingroup$ @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. $\endgroup$
    – idmean
    Jul 26 at 11:34
1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ thankyou for proper clarification. $\endgroup$ Jul 27 at 18:00
  • $\begingroup$ Glad to be useful. $\endgroup$
    – zkutch
    Jul 27 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.