# Estimate the running time of a while-for-while loop

i, sq ← 1, 1
while sq < n
for j ← 1 to sq
k ← 1
while k ≤ j
k ← 2 ∗ k
i ← i + 1
sq ← i ∗ i


I have expressed the running time of the "for" loop as a sum in this way :

$$\sum_{j=1}^{i^2} \log(j)$$

In a similar way, how can I express the running time of the outer "while" loop with sigma in terms of $$i$$ ? I have tried the following: $$\sum_{i=1}^\sqrt{n} i^2\log(i)$$

The outer most while loop ends when $$\text{sq} = n$$ and by definition $$\text{sq} = i^2$$ and thus it will run $$i^2 = n \Rightarrow i = \sqrt{n}$$ times ( as we increment $$i$$ by one each iteration).

Note that -
The for loop runs at $$\log(j)$$ from $$1$$ to $$\text{sq} = i^2$$ and $$1 \leq i \leq \sqrt{n}$$ so we have this sum:

$$\sum_{k=1}^{i^2}\log(k) ~~ \forall i \in\{1,2, \dots,\sqrt{n}\}$$

Recall: $$\log(a) + \log(b) = \log(a \cdot b)$$
Some examples:
$$i=1 \Rightarrow \sum_{k=1}^{1}\log(k) \Rightarrow \log(1!)$$
$$i=2 \Rightarrow \log(4!)$$
$$i=3 \Rightarrow \log(9!)$$
$$i=4 \Rightarrow \sum_{k=1}^{16}\log(k) = \log(1)+\log(2) + \dots + \log(16) \Rightarrow \log(16!) ~~~~~~ \\ \text{etc... until } i=\sqrt{n}$$

And thus this whole system of loops runs at:

$$\sum_{k=1}^{ \sqrt{n}}\log[(k^2)!] = \log{( \prod_{k=1}^{\sqrt{n}}k^2! )}$$
This can be bounded by $$O(\sqrt{n} \log(n!))$$ or $$O(n^{1.5} \log(n))$$ by taking the largest element in that sum ( $$\log(n!)$$ ) and multiplying it by the number of elements ( $$\sqrt{n}$$ )

• I can’t quite see where the factorial comes from. Commented Aug 31, 2020 at 8:52
• @gnasher729 Let's say $i=2$ then $sq=4$ and thus we iterate $j = 1 \dots 4$ and the inner while loop is $\log(j)$ so it is: $\log(1) + \log(2) + \log(3) + \log(4) = \log(1 \cdot 2 \cdot 3 \cdot 4) = \log(4!)$ IIRC - this happens for each $i = 1,2, \dots , \sqrt{n}$ Commented Aug 31, 2020 at 8:56
• @CSchofx can I bound the running time of for loop ∑_j=1 ^ i2 log(j) as theta(i^2 lg(i))? Commented Aug 31, 2020 at 12:23
• @Jon Anderson Sorry I don't understand the latex.. do you mean: $\sum_{j=1}^{i^2} \log(j) \in \Theta( i^2 \log(i) )$ ? Commented Aug 31, 2020 at 12:32
• @Jon Anderson This does hold: $\sum_{j=1}^{i^2} \log(j) = \log(i^2 !) \in \Theta( i^2 \log(i^2)) = \Theta( 2i^2 \log(i)) = \Theta( i^2 \log(i))$ Commented Aug 31, 2020 at 12:45

The innermost loop runs $$\lg(j)$$ times.

The middle loop executes it for all $$j$$ from $$1$$ to $$s$$, hence $$\displaystyle\sum_{j=1}^{s}\lg(j)=\lg(s!)$$.

The outer loop executes the latter for all perfect squares from $$1$$ to $$n$$, hence $$\displaystyle\sum_{k=1}^{\sqrt n}\lg((k^2)!)$$.

Using Stirling, we can approximate with $$\displaystyle\sum_{k=1}^{\sqrt n}k^2(2\lg(k)-1)$$, which is $$\Theta(n^{3/2}\log(n))$$, by integration.