@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 <vasa.san...@gmail.com> 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 <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- 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 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.
