1

I was trying to find the time complexity for a for loop. below is loop detail.

for(int i=N;i>1;i=i/2)
{
   for(int k=0;k<i;k++){
     sum++;
   }
}

Below is any find for the problem. Please correct me if i am going worng.

Inner loop will be exceute N+N/2+N/4+N/8....

so tn=ar^(n-1). So replacing Tn=1, a=N and r=1/2

1=N(1/2)^(n-1)

therefore 

1/2N=(1/2)^n

So sum of inner loop is a GP. Sn=a(1-r^n)/(1-r) Replacing a=N,r=1/2, we get

Sn=N(1-(1/2N))/(1-1/2)

therefore Sn=2N-1

I am not sure if complexity is N.

Please help

Thanks.

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32
user3264197
  • 31
  • 2
  • You would like to find out how much time this loop takes? –  Mar 14 '14 at 18:55
  • Just count the number of times the code in the inner loop is executed: `N + N/2 + N/4 + ...` – trogdor Mar 14 '14 at 18:57
  • 6
    On a piece of paper, make two columns, with headers "N" and "count". When N=1, how many times is `sum++` executed? For N=2, 3, 4, etc.? This will give you a start, and if you have questions, you can at least show this attempt. – Matt Mar 14 '14 at 18:57
  • 1
    Is this homework? It smells like homework. – Emmet Mar 14 '14 at 19:13
  • Actually I wouldn't really recommend what @Matt said as such (although *some* attempt is always better than *no* attempt for [so] questions) - having a bunch of values and mapping a function to that is not an easy task - rather write down how many times the inner loop executes for each iteration of the outer loop - this will give you something like `a + b + c + d + e + ...` (some of these will depend on `N`). Then you need to have a bit of familiarity with finding a formula for a sum, which gives you your answer. – Bernhard Barker Mar 14 '14 at 19:20
  • @Dukeling If he were to directly write down the number of iterations by skipping your step, then he would probably be smart enough to write the function too :) Naturally what I suggested would lead him through and motivate your analysis; you have added additional clarity to this process. Our suggestions are compatible, not mutually exclusive. – Matt Mar 14 '14 at 19:25
  • @user3264197 You may want to take a look at this related question: http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – jimm-cl Mar 14 '14 at 19:51
  • @trogdor: You still need to know the sum formula for the geometric series – Niklas B. Mar 14 '14 at 20:02
  • I did some analysis but i am not sure i am correct. Please find the detail. inner loop will execute as N +N/2+N/4.... 1=N(1/2)^(n-1). therefore (1/2)^n=(1/2N).. Now, Sn=a(1-r^n)(1-r)..therefore Sn=2N-1. I am not sure if inner loop has time complexity of 2N-1. – user3264197 Mar 14 '14 at 20:07
  • @user3264197: You need to *show your own attempt* in the question. Please consult the help center for information on [how to ask a question](http://stackoverflow.com/help/how-to-ask). – Niklas B. Mar 14 '14 at 20:08
  • @NiklasB. I wanted to give the asker a significant step to solve the problem without providing the complete answer, given the effort put in the question. Are you implying that I gave too much information, or that I should have posted the complete answer? – trogdor Mar 14 '14 at 20:15
  • @trogdor: I just noted that it is probably not helpful to figure *that* part out, but I don't really care either – Niklas B. Mar 14 '14 at 20:16
  • Thanks I will edit the question to show what attempt i have made. – user3264197 Mar 14 '14 at 20:19
  • @trogdor Personally I think you gave away too much, and too little (although OP seems to have a decent idea how to do it already, but assuming they didn't). A large part of this is to figure out each term of the sum, which you just gave away. Another part is finding the formula for the sum, which isn't really something you could just figure out if you don't have the maths knowledge to do so. – Bernhard Barker Mar 14 '14 at 21:16

1 Answers1

1

Below is the formal way (Sigma Notation) to infer the order of growth related to your algorithm (corroborated with experiments, using C's MinGW2.95 compiler).

enter image description here

Mohamed Ennahdi El Idrissi
  • 2,931
  • 2
  • 19
  • 32
  • I did not get the upper bound for second summation. How it is 2^i - 1. Could you please explain in detail – user3264197 Mar 14 '14 at 22:42
  • Well, you know that Sigma from i = k to n = (n - k) + 1? Since the terms of the second summation are independent, therefore, you just replace n with 2^{i - 1} and k with 0. I should end up with 2^{i - 1} - 0 + 1 (I will correct it). – Mohamed Ennahdi El Idrissi Mar 14 '14 at 22:46
  • Also, check this [link](http://www.wolframalpha.com/input/?i=sum%5B+1+%5D+with+k+from+0+to+%282%5E%28i+-+1%29%29). – Mohamed Ennahdi El Idrissi Mar 14 '14 at 22:50
  • Also, check the last slide of [this .ppt](http://faculty.kfupm.edu.sa/ics/jauhar/ics202/Unit03_ComplexityAnalysis1.ppt) for a thorough understand of logarithmic loops. – Mohamed Ennahdi El Idrissi Mar 14 '14 at 22:57
  • I'm 95% sure that anyone who understands this answer would've also fairly easily be able to determine the time complexity had they not seen it. As such, I don't think it's useful. – Bernhard Barker Mar 14 '14 at 23:59
  • I expect that anyone who's comfortable with the mathematical notation used in this answer would fairly easily be able to figure out the time complexity of such a simple algorithm (assuming they know the basics about time complexity - if not, this answer won't help either). Perhaps more significantly, it's non-trivial to figure out how you actually got to your **first** step, and some (most) of the intermediate steps probably need a bit of an explanation. – Bernhard Barker Mar 15 '14 at 00:52
  • 1
    I see your point. My aim is to allow interlocutors to discover that such a methodology does exist. I was thrilled when I discovered it, and where? in an algorithm analysis (and data structures) book of Mark Allen Weiss. I believe this is the right step toward the accurate learning path. – Mohamed Ennahdi El Idrissi Mar 15 '14 at 00:57
  • The solution underwent major alterations. – Mohamed Ennahdi El Idrissi Apr 11 '14 at 00:44