Mazdak Farrokhzad edited analysis setup.tex  about 10 years ago

Commit id: d814b4595902789a9f8a36a9d006a7517370b405

deletions | additions      

       

#8 end loop  \end{verbatim}  First things first, regarding line \#1 - we couldn't decide whether the array is an in-parameter and if the algorithm in that case begins by setting all elements in the array to true - in which case $n$ would have to be added to $T(n)$. In the section "Solving the sum" we haven't added it, but it would be trivial to do so, and in the end it wouldn't change the $\mathcal{O}$ (Ordo) complexity. complexity class.  Let any constant initial cost of the algorithm be denoted $a$. In this algorithm it is for example one might suspect that it would be the initialization of the for-loop at line \#2.  The body of the loop starting at line \#2 quite obviously runs from $2 \to \sqrt{n}$