[algogeeks] Re: Please help me!!!!
For the second question its not possible to do it in O(log n), as u need O(n) time to read the elements itself. You need to check your second question. There might be some constraints associated with the arrays. On 5/19/07, dor [EMAIL PROTECTED] wrote: 1. You can certainly do it in O(n log(n)) without any additional memory. Sometimes you can bring the complexity down using additional memory (i.e., hashing). 2. O(n log(n)) is trivial (sorting). There is a linear time algorithm for finding the median (I call it median of the medians, I don't know if it has a specific name). Here is a good description of the algorithm (see Linear Selection section): http://www.cs.princeton.edu/courses/archive/spring06/cos423/Handouts/notes%20on%20heapsort.doc On May 18, 10:33 pm, alkispe [EMAIL PROTECTED] wrote: Hello everyone i have 2 problems and i need the best algorithms and the complexity. Can you please help me? 1. Find if in an array there are some elements that appear more than one times 2. You have 2 arrays A and B.give the best algorithm for finding the median of the 2n elements of the two arrays Also for the 2nd question i need an algorithm with complexity O(log(n)). Please help me --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Why we need prime numbers?
Hi To cite an example , the RSA algorithm's working is based on the proof of the corollary to Euler's theorem. This corollary uses 2 prime numbers and hence RSA which derives its working from this theorem uses prime numbers. This was just an example..similarly there is some mathematical basis for most cryptographic algorithms, the use of prime numbers in the algorithms is because of the underlying mathematical theorem. On 6/13/07, Bin Chen [EMAIL PROTECTED] wrote: Hi, Many cryptography algorithm used prime to do the modular math, but I don't know why it need to use prime but not many ordinary numbers? Thanks Bin --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Why we need prime numbers?
On Jun 13, 7:36 pm, Raghav P [EMAIL PROTECTED] wrote: Hi To cite an example , the RSA algorithm's working is based on the proof of the corollary to Euler's theorem. This corollary uses 2 prime numbers and hence RSA which derives its working from this theorem uses prime numbers. This was just an example..similarly there is some mathematical basis for most cryptographic algorithms, the use of prime numbers in the algorithms is because of the underlying mathematical theorem. Yes, I really know the basic reason. Most encrypt algorithm's aim is to make the hacker can only decrypt the data by one method, which is brute force. So prime can make sure this, I guess, but how prime sure this? Which mathematical theorem can prove this? Thanks. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Why we need prime numbers?
Hi If u are asking as to why only prime numbers solve the mathematical theorems like Euler's corollary or Fermat's theorem then obviously its because of their basic nature. i dono what else is the reason On 6/13/07, Bin Chen [EMAIL PROTECTED] wrote: On Jun 13, 7:36 pm, Raghav P [EMAIL PROTECTED] wrote: Hi To cite an example , the RSA algorithm's working is based on the proof of the corollary to Euler's theorem. This corollary uses 2 prime numbers and hence RSA which derives its working from this theorem uses prime numbers. This was just an example..similarly there is some mathematical basis for most cryptographic algorithms, the use of prime numbers in the algorithms is because of the underlying mathematical theorem. Yes, I really know the basic reason. Most encrypt algorithm's aim is to make the hacker can only decrypt the data by one method, which is brute force. So prime can make sure this, I guess, but how prime sure this? Which mathematical theorem can prove this? Thanks. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Why we need prime numbers?
On Jun 13, 9:04 pm, Raghav P [EMAIL PROTECTED] wrote: Hi If u are asking as to why only prime numbers solve the mathematical theorems like Euler's corollary or Fermat's theorem then obviously its because of their basic nature. i dono what else is the reason I'd like to suggest you don't top post in google groups/USENET, it is very rude. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Why we need prime numbers?
On 6/13/07, Bin Chen [EMAIL PROTECTED] wrote: Many cryptography algorithm used prime to do the modular math, but I don't know why it need to use prime but not many ordinary numbers? I think it the it's the other way around! :-) Since there isn't any really efficient way to prime factorize really large numbers, many cryptography related algorithms base their method around large primes. Quote this (http://en.wikipedia.org/wiki/Prime_factorization_algorithm#Time_complexity) Wikipedia entry, ...The difficulty (large time complexity) of factorization makes it a suitable basis for modern cryptography. -- Rajiv Mathews --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
