2. Let n E N and b > 1. We have said that the simple loop below will go through
ID: 3747601 • Letter: 2
Question
2. Let n E N and b > 1. We have said that the simple loop below will go through exactly rio&n] 2, the answer is nl iterations (we usually write this iterations. In particular, when b as [log n]). while n>1 n:-n/b; end-while (a) Trace the execution for n :-25, b-3, i.e., trace the values of n. Do the same for n 5, (b) Suppose that b is replaced by b2. How does the number of iterations compare with (c) Suppose that b is replaced by Vb. How does the number of iterations compare with (d) Suppose that instead of dividing by b, we subtract b from n. How does the number of b 3/2. rlogbn)? Is it (logb n), (logb n), or O(logm)? logbn!? Is it (log n), (logm), or O(logm)? iterations connpare withlogbn!? Is it (logb n), (logbn), or O(logb n)?Explanation / Answer
(a) Execution for n=25 and b=3.Loop will executes 3 times before termination.In this case clearly no of iteration performed are upper_bound(logbn) as (logbn)=2.92
After 1st Iteration Value of n=8
After 2nd Iteration Value of n=2
After 3rd Iteration Value of n=0
Execution for n=5 and b=3/2.Loop will executes 3 times before termination.In this case clearly no of iteration performed are lower_bound(logbn) as (logbn)=3.96
After 1st Iteration Value of n=3
After 2nd Iteration Value of n=2
After 3rd Iteration Value of n=1
(b) When b is replaced by b2
As b>1 no of iterations will decrease. T(n)=upper_bound((1/2)*(logbn))
(use the log property----> log b*bn = (1/2) log b n ) so clearly T(n) < =c*f(n) where f(n)=logbn c=1 n0=1
so no of iteration would be O(logbN)
(c) When b is replaced by sqrt(b)
As b>1 no of iterations will increase almost equal to twice of pervious iterations. T(n)=upper_bound((2)*(logbn))
(use the log property----> log SQRT(b)n = ((2) log b n ) so clearly T(n) < =c*f(n) where f(n)=logbn c=3 n0=1
(d)When subtraction is performed instead of divison.
No of iterations in this case would be much more than logbn.
T(n)=n f(n)=logbn we Know N is naural number and b>1 Let c=1 and n0=1; then we have
n>(1.logbn) for n>=1 So So no of iterations will be (logbn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.