Order of Complexity

The binary to decimal conversion algorithm is of complexity O(k), i.e. the complexity of the loop. However, k is a count of the number of digits in the binary representation of x, that is log2x, thus this can also be treated as a algorithm of complexity O(log x)!

The decimal to binary algorithm contains a while loop that depends on the value associated with the variable identified as x, but the range is divided in half at each iteration. Thus this is similar to the binary search algorithm and is of complexity O(log x) also!


Last updated 2002/02/04
© J.A.N. Lee, 2002.