File EditView Go Tools Window Help @? 89% us. Thu Sep 27 4:45:24 PM CMP340 Homew

Question

File EditView Go Tools Window Help @? 89% us. Thu Sep 27 4:45:24 PM CMP340 Homework1-2 pdt (page 2 of 2) O. Q Search Q4) [5 points] Consider the following two algorithms: ALGORITHM1 BinRec(n) //Input: A positive decimal integer n s in n's binary representation ifn 1 return 1 else return Bin Rec(Ln/2) +1 ALGORITHM 2 Binary(n) //Input: A positive decimal integer /Output: The number of binary digits in n's binary representation count 1 while n > 1 do count count + 1 n |n/2] 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.

Explanation / Answer

Analysing the above two algorithms on the basis of time and space complexity below:

1> Time Complexity -
Algorithm 1 - considering n = 8; the algorithm calls the function BinRec for numbers 8,4,2,1 which is 4 times (i.e: n/2 times) so the time complexity for algorithm 1 will be O(n/2)
Algorithm 2 - again considering n = 8; the loop repeat itself for 8,,4,,2,1. which is 4 times (i.e : n/2 times) so the time complexity will be O(n/2)

So looking at the time complexity both the algorithms stand at the same position

2> Space Complexity -
Algorithm 1 - considering it requires m units of memory to create the object for the function BinRec and its varibles and it is called n/2 times, so the space complexity will be O(nm/2)
Algorithm 2 - In this algorithm we don't create extra variables count to store the variable so the which require 1 unit of memory and it updated everytime the same variable so we are not adding any extra memory so the space complexity will be O(1)

So looking into the space complexity Algorithm 2 is better then Algorithm 1 O(1) is better then O(nm/2)

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.