Mazdak Farrokhzad edited analysis setup.tex  about 10 years ago

Commit id: 4f4ff458d4a70d3009be569278d6083d6a490c69

deletions | additions      

       

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.  Imagine a loop from $i \to n$ that steps by $x$ each time. Such a loop will by definition run $\frac{n}{p} - \frac{i}{p} + 1$ times.  This is exactly what the loop from line $\#4 \to \#6$ does, but we have rewritten it to use step-size 1, instead, dividing the starting and ending point both by $p$. This loop has a constant cost $c$ per iteration and costs: $\sum_{m=p}^{\frac{n}{p}}$. $\displaystyle\sum_{m=p}^{\frac{n}{p}} c$.