0
$\begingroup$
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)$$

$\endgroup$

2 Answers 2

1
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ I can’t quite see where the factorial comes from. $\endgroup$
    – gnasher729
    Aug 31, 2020 at 8:52
  • $\begingroup$ @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}$ $\endgroup$
    – CSch of x
    Aug 31, 2020 at 8:56
  • $\begingroup$ @CSchofx can I bound the running time of for loop ∑_j=1 ^ i2 log(j) as theta(i^2 lg(i))? $\endgroup$ Aug 31, 2020 at 12:23
  • $\begingroup$ @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) )$ ? $\endgroup$
    – CSch of x
    Aug 31, 2020 at 12:32
  • $\begingroup$ @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)) $ $\endgroup$
    – CSch of x
    Aug 31, 2020 at 12:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.