helo, thank you for the reply.
> The algorithm you describe is linear, not log. > Complexity measures are a > function of the size of the input data set in bits. > In general, a large > integer M will require an input around N = LOG2(M) > bits to represent. If we are to convert a k-bit integer n to a base b number,it takes us O(log n) if the base b is a power of 2 is still a correct statement. Say if we are to multiply a k-bit integer n with the same k-bit integer n, i.e multiplying integer n with k-bits by itself. The multiplication takes atmost k^2 bit operations. eg. n=5=101 base 2. i.e the multiplication takes atmost 3^2=9 bit operations. Thus multiplication of O(k^2) for a constant c and n>=no. All logarithms are to the base 2. Since k=[log n]+1 k^2=([log n]+1)^2 in our example = ([log 5]+1)^2 =3^3=9 operations. it is correct to write O(log n)=O(k), as n or k are the inputs to an algorithm whose time complexity is to be determined. O(log n)=O(k)is the time the algorithm takes for processing the input which are essenctially the same. > You ask whether there are linear algorithms for > arbitrary precision base > conversion. yes,I was asking if there is an algorithm in O(k)=O(log n) to convert a k-bit integer n to arbitrary base. I only know to do it in O(k^2). thanks, Sarath __________________________________ Do you Yahoo!? The New Yahoo! Shopping - with improved product search http://shopping.yahoo.com
