Mazdak Farrokhzad edited analysis setup.tex  about 10 years ago

Commit id: e32c7781c94ddf910620eea9e72b5bd8b412fc3b

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: $\displaystyle\sum_{m=p}^{\frac{n}{p}} c$. c$ for the entire loop.