# Runtime of algorithem when the internal for depend on the external for

I'm trying to find the running time of this pseodocose:

int x=0,i,j
for (i=1;i<=n;i++)
for(j=1;j<=n+r;j=j+i)
x=x+j;


What I did: First I checked what happened on the first iteration of the external for:

• $i=1:$ the internal for will run $n+r$ times, so $j\in\{1,2,3,4,\dots,n+r\}$ so $\color{blue}{a_n=n}$

• $i=2:$ the internal for will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\{1,3,5,7,\dots,k\}$ so $\color{blue}{a_n=2n-1}$

• $i=3$: the internal for will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\{1,4,7,10,\dots,k\}$ so $\color{blue}{a_n=3n-2}$

So the runnig time should be $\color{blue}{\underbrace{n+(2n-1)+(3n-2)+(4n-3)+\dots}_{ n+r \text{ times}}}$

But what should I to now? I should find the running time in $\Theta$ terms, I am trynig to find the runnig time without using any calculator

• The first step would be to correct your calculations. Try writing a program that computes the number of times the second loop is run, and compare it to your calculation. The second step would be to sum the resulting series. – Yuval Filmus Mar 18 '16 at 11:52
• There are plenty of questions about algorithm-analysis+loops, including our reference question. I recommend you look there and find out how to express the costs more rigorously, i.e. get rid of "...". (Nitpick: you are not really analysing "running time". What is it you are counting?) – Raphael Mar 18 '16 at 13:51

For $i=1$ the internal loop runs for $n+r$ times, for $i=2$ the internal loop runs for $\lceil (n+r-1)/2 \rceil+1$ times, for $i=3$ the internal loop runs for $\lceil (n+r-1)/3 \rceil+1$ times, and so on till $i=n$ when the internal loop runs for $\lceil (n+r-1)/n \rceil+1$ times.