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?


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.