1. 4 marks Binary representation and algorithm analysis. Consider the following

Question

1. 4 marks Binary representation and algorithm analysis. Consider the following algorithm, which manually counts up to a given numbernsing an array of 0's and 1's to mimic binary notation. a from math import floor, log2 4 def count (n: int) -> None: # Precondition: n > 0 p- floor (log2(n)) + 1 bits [o]p # The number of bits required to represent n # Initialize an array of length p with all 0's for i in range(n) : #i "0, 1, n-1 , # Increment the current count in the bits array. This adds 1 to # the current number, basically using the loop to act as a "carry" operation while bits[j]1: 13 14 15 ??? bitsj]-0 bitstj For this question, assume each individual line of code in the above algorithm takes constant time, i.e., counts as a single step. (This includes the op line.) (a) 3 marks] Prove that the running time of this algorithm is O(n log n) (b) mark Prove that the running time of this algorithm is 2(n)

Explanation / Answer

Worst Case

Here the for loop runs n times. Inside the for loop there is while loop which runs upto length of bits array.

Length of bits array is log n.

Hence the worst case complexity is O(nlogn).

Best case complexity

In best case all bits[i]=0. Then the inner while loop will not work.

Hence the best case complexity is ?(n)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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