Analyzing runtime of a nested for loop

Question

// assume n is a power of 5
for (int i=1; i<n; i=i*5)
    for (j=i; j<n; j++)
        sum = i+j;

I am supposed to find out how many times each line of code runs. I was told that I would need to use the geometric series formula to find the total run time.

I know that the first line of code for (int i=1; i<n; i=i*5) runs $\log_5n$ times because the values of i are $5^0,5^1,5^2, ... , 5^k$ and this is equal to $k=\log_5n$.

The runtime of the inner for loop for (j=i; j<n; j++) decreases by $1$ after each iteration. I found that on the first iteration this loop runs ntimes. On the second iteration the loop runs n-4times, on the third it runs n-124 times.

I think the sequence is $n, (n-4), (n-24), (n-124),...,(n-5^k +1)$ each term can be found by the formula $n-5^k+1$ where $k$ is the kth term in the sequence (starting from $0$).

How do I find the sum of this sequence using the geometric series formula?

I wasn't sure what upper bound I would use for the summation so I used an arbitrary variable m.

$\sum_{k=0} ^{m}n-5^k+1 = (n+1)\dfrac{1-5^{m+1}}{1-5}= (n+1)\dfrac{1-5^{m+1}}{-4} $

Is this the correct approach to this problem?

Answer 1

You correctly found that the j<n test in the second line is executed a total of $$\sum_{h=0}^m (n-5^h+1)$$ times, for some integer value of $m.$ This is almost the formula for the total number of iterations of the inner loop (the number of times the third line runs), which is $$\sum_{h=0}^m (n-5^h)$$ for the same value of $m.$ That's because the first inner loop actually executes only for the values $1,2,3,\ldots,n-1,$ which is a total of $n-1$ iterations, not $n,$ and similarly it does not execute when $j$ is $n$ at any other time.

(I changed $k$ to $h$ in the summation because you already used $k$ to mean something else, $k = \log_5 n,$ and while it is technically permissible to reuse $k$ as the variable of summation in this case, it is confusing.)

There is a particular value of $m$ that you should use. Consider what the value of $i$ is on the last iteration of the outer loop, and how that relates to your variable $k.$

Notice that if $k=\log_5 n$, then $5^k = n.$ The outer loop will not actually call the inner loop for $i=n$ because of the condition $i<n.$ So you have iterations for $i=5^0,5^1,\ldots,5^{k-1}.$ (In this particular problem it turns out the answer is the same whether we execute the inner loop for $i=5^k=n$ or not, but in general if you want to count an exact number of operations then it's advisable to keep track of when each loop ends.)

So we can conclude that the last value of $h$ for which we need to add a term of the sum is $h=k-1,$ which counts the last $n-5^{k-1}$ iterations of the inner loop. The sum that counts the number of times the third line runs is therefore $$\sum_{h=0}^{\log_5n-1} (n-5^h) = \left(\sum_{h=0}^{\log_5n-1} n\right) - \left(\sum_{h=0}^{\log_5n-1} 5^h\right).$$ Now we can see a geometric series in the result, and the other part of the result is even easier to evaluate.