I am currently working on the asymptotic analysis of Karatsuba algorithm and I have this linereturn (X * B^ (2 * m)) + ((Z) * B ^ (m)) + (Y)where X,Z,Y are some numbers, m is in fact floor(n/2), where n is the length of the input, and B is a base(could be 10, then we would have decimal numbers).I was wondering whether someone could help me with calculating the complexity of ((Z) * B ^ (m))Multiplication is always Theta(n^2), but the whole algorithm has Theta(n) in the solutions. I know that the cost of performing an addition is Theta(n), but what would be the cost of the that function, given I have already calculated Z.I have also written a code, which instead of multiplying the numbers, just shifts them, and I believe that would have cost of Theta(n). Is this the case that I can always shift no matter what base I use?Thanks!
Asymptotic analysis of shifting/multiplying
algorithm analysis;runtime analysis