potential method algorithm We are given n textbooks each of weight n. The goal i
ID: 3669914 • Letter: P
Question
potential method algorithm
We are given n textbooks each of weight n. The goal is to shrink the weights of all textbooks to 1 or less. The process goes as follows: in each step a subset A of textbooks with weight greater 1 is chosen and the weight of each textbook in A is shrunk by a factor of (1 + 1/|^4|). Note that the choice of A in each step can be arbitrary. The process halts when the weights of all the textbook are less or equal to 1. Note: you may find the following inequality useful: If we have x such that 0Explanation / Answer
we are given n text books each of weight n.
So for each text book, it take (1+1/|A|)
a)
consider we have n text books ...
every time we will process one text book, it take (1+1/|A|)
So for second step, another text book ..
(1+1/|A|) + (1+1/|A|)
So, for n text books it take
(1+1/|A|) + (1+1/|A|) + .... + (1+1/|A|) ----> n steps
so n + n(1/|A|) steps
---------------------------------------------------------------------------------------
b)
In each step if takes all text books in a single step, then
then it starts shrunk by factor (1+1/|A|)
So regardless of queue .. it process one by again ..
So it takes again n + n(1/|A|) steps steps.
-----------------------------------------------------------------------------
c)
For this scenario .. we will write potentil function.
So, for n text books it take
(1+1/|A|) + (1+1/|A|) + .... + (1+1/|A|) ----> n steps
so n + n(1/|A|) steps
In big oh notation ..
n(1+(1/|A|)) ===> n(1+n(1/|A|)) can be written as n * (log1 + (logn - log(|A|)) ..since(log(a/b) = loga-logb)
By ignoring log(|A|) since, for every iteration it gets reduce and we can negotiate it.
So n(log1 + log(n)) ==> since log1 = 0 ==> therefore n(logn)
Total number of steps is given in big-oh notation is O(n log n)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.