Question

Q4) [5 points] Consider the following two algorithms: ALGORITHM 1 Bin Rec(n) //Input: A positive decimal integer n llOutput: The number of binary digits in "'s binary representation if n1 return 1 else return BinRec(ln/2)) +1 ALGORITHM 2 Binary(n) tive decimal integer nt io 's binary representation //Output: The number of binary digits in i's binary representation count ←1 while n >1 do count ← count + 1 return count a. Analyze the two algorithms and find the efficiency for each of them. Hint: You may use the recurrence relation instead of the summation to analyze the nonrecursive algorithm. b. Which algorithm is more efficient? and why?

Answer 1

Algorithm 1: This algorithm divides each problem into sup program of size half in each recursion T(n) = T(n/2) + O (1) for base case check T(n) = O(log_2 n) But each recursive will need one extra stack frame on stack until n = 1: Hence space complexity is let n^k = 1 S (n) = log n Algorithm 2: while loop breaks n into n/2 and no extra space is required because it is according only one stack frame. T(n) = n/2 + n/4 + ---- 1 = O (log_2 n) Hence Algorithm 2 is best as both have same Time complexity but space complexity of Algorithm 2 is constant.