Hi EPI,
In the solution, the brute force time complexity is given as O(2^n) where n is the number of bits in the integer type.
Could you please expand on this? I was under the impression that multiplying two integers of n bits would give O(n^2) time complexity and since the brute method does this y-1 multiplications, we have y-1 * O(n^2) = O(n^2).
The explanation here is like we have n bits to represent y, and the maximum of y can be 2^n, so the number of multiplications you need to have from x^1 to x^y is actually (y-1) times. Those is actually O(2^n).
Why is multiplication O(n^2)?
In other resources I got the impression that all basic arithmetic operations (such as addition or multiplication) are considered one CPU instruction, meaning O(1).
It is not if you view this problem from the number of bits it touches. Assuming the number of bits is O(n), then multiplication is definitely O(n^2)