1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Mar 18 '16 at 11:52
  • 1
    $\begingroup$ 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?) $\endgroup$ – Raphael Mar 18 '16 at 13:51
1
$\begingroup$

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.

You now need to sum these numbers. I suggest you read about harmonic series.

$\endgroup$

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.