4.7 - Compute x^y - C++


#1

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).


#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).


#3

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).


#4

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)


#5

Really helpful, thank you