On complexity of the sieve, start crossing at the square of $p$ This question is about a common optimization in the basic sieve of Erathostenes. 

If we look at this paper (page 3, footnotes), the author says:


  If we start crossing off at $p^2$ rather than $p$, the number of composites
  we cross off is $\frac{n}{p}−p+1$, but it makes no significant difference to our
  sum, because it only subtracts an irrelevant $O(n/ \log n)$ factor


Similarly, I have seen the same conclusion in other places, so according to them we have that the total cost counting crossings is about (ignoring the $\sqrt n$ optimization):

$\sum_{p\leq n}(\frac{n}{p}-p+1)$

Where $p$ is prime.

But if we look at this algorithm (in pseudocode) implementing this same optimization:

//omitting sieve[2..n] initialization
for p:=2 to n 
   if (sieve[p] is prime)
      for k:=p^2 to floor(n/p)
         sieve[k*p] := not prime     //cross multiples of p


I would say the total cost is:

$\sum_{p\leq n}(\frac{n}{p}-p^2+1)$

because the cost of the inner loop is 

$\sum_{k=p^2}^{\frac{n}{p}}=\frac{n}{p}-p^2+1$

Am I wrong?
Your algorithm is wrong. The starting point should be $p$ rather than $p^2$, since in the body of the loop $k$ gets multiplied by $p$.