# Asymptotic analysis of shifting/multiplying

I am currently working on the asymptotic analysis of Karatsuba algorithm and I have this line

"return (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!

• What is n here? What cost model do you use? See also here. – Raphael Mar 4 '15 at 6:02
• n is just the length of the input. – Johhny Bravo Mar 4 '15 at 12:22
• It just seems to me that you throw multiple, different n around there. – Raphael Mar 4 '15 at 12:29
• Well, n denotes always the length of the input. – Johhny Bravo Mar 5 '15 at 2:55