Cheap and Secure Web Hosting Provider : See Now

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

, , No Comments
Problem Detail: 

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

Asked By : Nehorai

Answered By : Shreesh

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54623

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback