For the code, here u go http://ideone.com/js1yV
On Wed, Jun 29, 2011 at 10:49 AM, Dave <[email protected]> wrote: > @Sanket: You are wrong. Let T(n) be the time to solve the problem of > size n. Then T(n) satisfies a recurrence T(n) = n + T(n/2). That is > because after you have done n reads, you have determined whether the > last bit is 0 or 1. To continue the solution, you only need to > consider those numbers that have the correct last bit, which is half > of the numnbers. This is equivalent to solving a problem of half the > size, which takes T(n/2). Thus T(n) = n + T(n/2). T(n) = 2n is a > solution to this recurrence, as you can verify by substitutine 2n for > T(n) and n for T(n/2) and seeing that the statement is true. Thus, the > problem can be solved in O(n) time for any value of n. > > Dave > > On Jun 28, 5:40 pm, Sanket <[email protected]> wrote: > > @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 <[email protected]> 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 <[email protected]> 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 <[email protected]> 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 [email protected]. > > > > To unsubscribe from this group, send email to > > > > [email protected]. > > > > 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- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Atul Purohit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
