Subject- Algorithms : Techniques and Theory

1. (15 points) Let S denote the set of all positive integers of the form 3i5j where i and j are nonnegative integers. Thus the smallest five numbers in S are 1,3,5,9, and 15. For any positive integer k, let f(k) denote the k th smallest number in S (indexing from 1 ); thus f(1)=1,f(2)=3,f(3)=5,f(4)=9, and f(5)=15. For any positive integer k, let g(k) denote the number of bits in the binary representation of f(k); thus g(1)=1,g(2)=2,g(3)=3,g(4)=4, and g(5)=4. Derive a -bound for g(k). Hint: Establish the upper and lower bounds separately