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 outer while loop with sigma in terms of i ? I have tried the following: $$\sum_{i=1}^\sqrt{n} i^2log(i)$$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I can’t quite see where the factorial comes from. $\endgroup$ – gnasher729 Aug 31 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 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$ – Jon Anderson Aug 31 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 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 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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