1

I am trying to convert instances of nested 'for' loops into a summation expression. The current code fragment I have is:

for i = 1 to n:
    for j = 1 to n:
        if (i*j >= n):
            for k = 1 to n:
                sum++
        endif

Basically, the 'if' conditional is confusing me. I know that the loops prior will be called n^2 times, but the third loop is only called when $i*j >= n$. How would I write the third summation to account for this, and then evaluate the overall loop's time complexity?

bpryan
  • 65
  • 1
  • 7
  • This is often context dependent. If, say, you wanted to iterate over the entries $a_{ij}$ of an $n \times n$ matrix, then the first two loops in your code sample could be adequately expressed as $$\sum_{ij \geq n} a_{ij}$$. Perhaps if you provided more context about why you have this problem we will be able to provide more helpful answers. – Brian61354270 Mar 26 '19 at 01:18
  • You want to convert the nested loops into a summation, but then you say you want to evaluate the time complexity of your code, which does not require you to convert the loops into a summation, and, in fact, does not require you to find what value sum has after the loops. – Fabio Somenzi Mar 26 '19 at 03:15

3 Answers3

1

Hint:

The "for" cycle in $k$ is very easy to turn into something simpler...

As for the other parts, see if you can split the problem into easier steps. For example, what happens for $i=1$? And what happens for $i=2$? And $i=3$? And...

Ertxiem - reinstate Monica
  • 1,664
  • 3
  • 11
  • 15
0

We obtain \begin{align*} \color{blue}{\sum_{i=1}^n}&\color{blue}{\sum_{j=1}^n[i j\geq n]\sum_{k=1}^n1}\tag{1}\\ &=n\sum_{i=1}^n\sum_{j=1}^n[i j\geq n]\\ &=n\left(\sum_{i=1}^n\sum_{{j=\left\lfloor n/i \right\rfloor}\atop{i\mid n}}^n1+\sum_{i=1}^n\sum_{{j=\left\lfloor n/i \right\rfloor+1}\atop{i\not \mid n}}^n1\right)\tag{2}\\ &=n\left(\sum_{i=1}^n\sum_{j=\left\lfloor n/i \right\rfloor+1}^n1+\sum_{{i=1}\atop{i\mid n}}^n1\right)\\ &=n\left(\sum_{i=1}^n\left(n-\left\lfloor\frac{n}{i}\right\rfloor\right)+\tau(n)\right)\tag{3}\\ &=n\left(n^2-\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor+\tau(n)\right)\\ &\,\,\color{blue}{=n\left(n^2-\sum_{i=1}^{n-1}\tau(i)\right)}\tag{4}\\ &\,\,\color{blue}{\sim n^3-n^2\left(\log n+2\gamma-1\right)+O\left(n^{3/2}\right)}\tag{5} \end{align*}

Comment:

  • In (1) we use Iverson brackets to represent the condition $ij\geq n$.

  • In (2) we rewrite the expression using the floor function. Note the $\pm 1$ technicality regarding the range of summation.

  • In (3) we simplify the inner sum of the left-hand term and use the $\tau$-function which counts the number of divisors.

  • In (4) we use an identity stated in A006218 to get rid of the floor function.

  • In (5) we use an asymptotic expansion which is also stated in OEIS/A006218.

Markus Scheuer
  • 108,315
0

At the basic level, for loops are also rewritable as conditionals. Anyways, on to the meat of the problem. The conditional can be removed if you replace 1 in the previous loop with ceil(n/i). So it can be rewritten as:

for i = 1 to n: for j = ceil(n/i) to n: for k = 1 to n: sum++

Then the inner 2 loops compress to:

sum+=n*(n-ceil(n/i)+1)

Which then gets called n times, but the sum can be wriiten as:

$$n\sum_{i=1}^{n}(n-\lceil\frac{n}{i}\rceil+1)$$

As to the time complexity of the code as wriiten..., it'll take, okay I don't quite know that part.