# Analyzing runtime of a nested for loop

// 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?

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.

• When $i = 5^{k+1}$, j iterates through the values $5^k -1, 5^k, 5^k +1, ..., n$ How would I find the sum of this? Is this value needed in order to find the summation? – user185714 Nov 10 '14 at 0:35
• Where did $5^{k+1}$ come into this? Also, you don't need to sum the values that $j$ actually takes, just count them. You were adding almost the correct sequence, you were just off by $1.$ The last value of $j$ for which sum = i + j executes is always $n-1,$ never $n,$ so you should be adding $(n-1)+(n-5)+(n-25)+\cdots+(n-5^{k-1})$ rather than $n+(n-4)+(n-24)+\cdots.$ – David K Nov 10 '14 at 2:31
• I think I was off by $1$ because I was calculating the runtime for the inner for loop, not sum = i + j. Since the inner for loop has to check it's condition for failure for every iteration of i, wouldn't I have to include it in the calculation? I also meant to say $5^{k-1}$ which is the last time i executes it's code. – user185714 Nov 10 '14 at 2:55
• Good point: j++ and j<n each execute one extra time compared to sum = i + j. The question did say we had to count how many times each line executed, so take my sum for the last line and your sum for the second line. In evaluating your sum it may help to write $n+1-5^h.$ You can then sum the $n+1$ and the $5^h$ separately. – David K Nov 10 '14 at 3:01
• Oops, that's $n - 5^h + 1$ times we execute j<n, but j++ is still done only $n - 5^h$ times; but j=i is also done once. It's a little unclear what is meant by "how many times this line runs" when the line is a control statement with multiple sub-parts. – David K Nov 10 '14 at 3:05