3 ms·
Can you explain what representation you use to get multiplication by a constant in O(log n)? Wouldn't it be at least O(n) for the standard bignum representation
by jules 16y ago
Can you explain what representation you use to get multiplication by a constant in O(log n)? Wouldn't it be at least O(n) for the standard bignum representations, making the algorithm O(n^2).
Multiplying n primes together creates an O(n) digit number. Multiplying an O(n) digit number by a constant is an O(n) operation. So essentially we're doing an O(n) operation n times, hence O(n^2).
The smartest representation that I can think of for the numbers would be to store the prime factor exponents in an array, which would essentially transform the algorithm into the array based version. For example 120 = 2^3x3x5 would be represented as {3,1,1,0,0,...}.
- nostrademons 16y agoIt's O(n) in the number of bits. The number of bits is O(log n) in the value of the number. Multiplying n primes together, where the primes are taken from a restricted set of numbers, creates a number whose value is O(n) (it has n factors, but each factor is bounded by a constant). BTW, I would've used a bitvector. For lowercase letters only, you could fit it into a 32-bit value (add mixed-case and numbers and you can fit it into 64 bits), then it's just an OR to set a bit and an AND to read if a bit has been set, both fast machine-level operations. Edit: Didn't see the footnote on the problem. A bitvector doesn't work if counts must be kept, but you can still do this pretty simply with the table solution.
- jules 16y agoSo, the resulting algorithm would be O(n^2) not O(n) where n is the length of the string. The table based solution is exactly like keeping the exponents in an array.