our aim here is to examine ways to measure how efficient this procedure is and attempt to answer the questionis this the most efficient procedure we can use for multiplying two large numbers togetherin the following figurewe can see that multiplying two digit numbers together requires multiplication operationsand we can generalize to say that an digit number requires approximatelyn multiplication operationsthis method of analyzing algorithmsin terms of the number of computational primitives such as multiplication and additionis important because it gives us way to understand the relationship between the time it takes to complete certain computation and the size of the input to that computation in particularwe want to know what happens when the inputthe number of digitsnis very large this topiccalled asymptotic analysisor time complexityis essential to our study of algorithms and we will revisit it often during this and the rest of this book can we do bettera recursive approach it turns out that in the case of long multiplication the answer is yesthere are in fact several algorithms for multiplying large numbers that require less operations one of the most wellknown alternatives to long multiplication is the karatsuba algorithmfirst published in this takes fundamentally different approachrather than iteratively multiplying single digit numbersit recursively carries out multiplication operations on progressively smaller inputs recursive programs call themselves on smaller subsets of the input the first step in building recursive algorithm is to decompose large number into several smaller numbers the most natural way to do this is to simply split the number in to two halvesthe first half of most significant digitsand second half of least significant digits for exampleour four-digit number becomes pair of two-digit numbers and we can write more general decomposition of any digit numbersx and using the followingwhere is any positive integer less than