An edgy case...
On Sun, Aug 1, 2010 at 9:52 AM, Shiv ... <shivsinha2...@gmail.com> wrote:
> What about this-
> =========
> long multiply(long num, int n) {
> long bigSum=0;
> while(n>=1) {
> int sum =num; int j*=1*; //to avoid garbage @n=1.
> for(int i =2; i<=n; i= i*2) {
> sum+=sum;
> j=i;
> } //for
> n = n -j;
> bigSum=bigSum+sum;
> }//while
> return bigSum;
> }//multiply()
> =======
> It's *O(logn).*
>
> On Sun, Aug 1, 2010 at 8:54 AM, Apoorve Mohan <apoorvemo...@gmail.com>wrote:
>
>> If suppose
>>
>> we want to Do N*K
>>
>> then we add N K-times or K N-times.
>>
>> hence the complexity should be O(N*K)
>>
>> On Sat, Jul 31, 2010 at 9:12 PM, Dave <dave_and_da...@juno.com> wrote:
>>
>>> If by "repeated addition method," you mean
>>>
>>> m + m + m + ... + m (where m occurs k times)
>>>
>>> for forming the product k*m, then the work of forming k*m where k and
>>> m are n digit numbers is O((k-1)*n).
>>>
>>> Using the elementary school algorithm, the work can be reduced to
>>> O(n^2).
>>>
>>> See http://en.wikipedia.org/wiki/Multiplication_algorithm for even
>>> faster algorithms.
>>>
>>> Dave
>>>
>>> On Jul 31, 7:58 am, sourav <souravs...@gmail.com> wrote:
>>> > When you first learned to multiply numbers, you were told that x * y
>>> > means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is
>>> > the time complexity of multiplying two n-digit numbers in base b using
>>> > the repeated addition method, as a function of n and b. Assume that
>>> > single-digit by single-digit addition or multiplication takes O(1)
>>> > time.
>>> >
>>> > Show how you arrive at your answer.
>>> >
>>> > (Hint that was given : "how big can y be as a function of n and b?")
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> regards
>>
>> Apoorve Mohan
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@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.
