[EMAIL PROTECTED] writes: > So this is no better than just having an array of the counts per > character, in terms of space and worse in terms of speed. :-/
Actually, what was I thinking, the radix approach would be better, spacewise. In terms of space it would require O(w) space where w is the number of bits used for the determination. The array of sums approach (what Pramod Patangay suggested earlier) requires O(K) space where K is the number of characters. Since w is logK or less, the radix approach is better. Speedwise, the array of sums would be O(2N), while the radix is O(2N*w). Both are O(N) since w is a constant relatively small, in case of huge N. [boy, I just replied to my own message for a second time :-)] --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
