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

Question

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)$$

Answer 1

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}$ )

• gnasher729: I can’t quite see where the factorial comes from.
• 0Interest: @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}$
• Jon Anderson: @CSchofx can I bound the running time of for loop ∑_j=1 ^ i2 log(j) as theta(i^2 lg(i))?
• 0Interest: @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) )$ ?
• 0Interest: @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)) $

Answer 2

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.