@Sunny - I would disagree. Assume there is a nested loop iterating over an array and for every iteration of the outer loop, you are reducing the number of elements accessed in the inner loop into half. So, in the first iteration of the outer loop, you access n elements in the inner loop, in the second iteration, you access n/2 and so on. Would you classify this as O(n) or O(n^2) ? When computing the complexity, we do not look at the "actual" number of elements processed. Hence, even though the series you mentioned sums upto 2n, you need to look at the possibility of how many times the "n" is going to occur and in this case, it is going to occur 'k' times, where k is the number of bits in the numbers.
On Jun 27, 12:34 pm, sunny agrawal <sunny816.i...@gmail.com> wrote: > @saket - No > O(n) + O(n/2) + O(n/4)................... = O(n) > > sum of series > n+n/2+n/4+n/8............ = 2n > > > > On Mon, Jun 27, 2011 at 9:26 PM, Sanket <vasa.san...@gmail.com> wrote: > > @Dave - Wouldn't your solution also become O(kn) where k = number of > > bits in the number? > > In this summation - O(n) + O(n/2) + O(n/4) + ...= O(n) - you would > > have O(n) appearing 'k' times. Each entry is O(n/ 2^i) where 'i' is > > the bit position from right to left, starting at 0. The range of 'i' > > is from 0 to 'k-1' > > Please correct me if I am wrong. > > > On Jun 27, 7:29 am, Bhavesh agrawal <agr.bhav...@gmail.com> wrote: > > > can anyone plz post the code for this problem > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Sunny Aggrawal > B-Tech IV year,CSI > Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
