What about this-
=========
long multiply(long num, int n) {
long bigSum=0;
while(n>=1) {
int sum =num; int j;
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.
