To make things more clear, we rewrote the algorithm so that it only uses for-loops.
The rewritten algorithm looks like:
#1 prime: array [1..n] of boolean = all true
#2 for p in 2..sqrt(n) loop
#3 if prime[p] then
#4 for m in p..n loop
#5 prime[m * p] = false
#6 end loop
#7 end if
#8 end loop
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 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.
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 starting at line \(\#4\) did, 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\) for the entire loop.
The inner loop is in turn run inside an outside loop which runs from \(2 \to \sqrt{n}\) and has an additional (excluding the inner loop) constant body cost \(b\) per iteration.
Therefore the total cost of the algorithm can be expressed as: \[T(n) = a + \sum_{p = 2}^{\sqrt{n}}\left[b + \sum_{m = p}^{\frac{n}{p}} c\right]\]