3. (a) Consider the following algorithm. Input: A real number x. (1) Set k=1. (2) If kx is an integer, stop and output k. Otherwise, go to (3). (3) Replace k by k +1 and go to (2). Prove that this algorithm terminates if and only if x is a rational number. (b) Find an infinite set of functions fi(n), f2(n), f(n),... such that all of the following properties are satisfied: Each of the functions fi(n), f2(n), f3(n), ... grows faster than the function 1 5n nn The function grows faster than each of the functions fi(n), f2(n), f3(n),.... 5n For every integer i > 2, the function fi(n) grows faster than the function fi-1(n). Note: you must write down formulas for your functions (in terms of n) and prove that your functions have the required properties