4. (10 points) Fill in the blanks below with complexity results stated in terms

Question

4. (10 points) Fill in the blanks below with complexity results stated in terms of n Assume print produces one line of output (a) Fragmernt for i-n downto 1 print(n + " bottles of beer on the wall, "+ n + " bottles of beer") print("you take one down, pass it around, ") print((n-1) + " bottles of beer on the wall") end The above fragment prints (b) Fragment for i-1 to n print("On the + i + "th day of Festivus my true love gave to me") for j-i downto 1 print(i + " nifty "+i+ "-things") end end The above fragment prints e lines (c) Fragment for i-1 to n int[] array = new int [5]; end Worst-case, the above fragment takes e time (d) Fragment for i-1 to n int[] array = new int [i]; end Worst-case, the above fragment takes e time. (e) Fragment while (i > 0) print("Zeno is almost there") i-i/2 // integer division and result end Worst-case, the above fragment prints (--) lines

Explanation / Answer

Question 4)

a) loop runs for n times and each time 3 print statements are executes

so total lines = 3*n which can be taken as a Theta(n)

b) When i = 1 , j = 1 to 1 i.e. 1 time

i=2, j = 2 times

i=3,j=3 times

So on when i=n, j =n times

Finally the outer pritnf runs for n times and inner printf runs for 1+2+3+----+n times

Total lines printed = n+ (n*(n+1)/2) lines

c) Loop runs n times so worst case can be Theta(n) times.

d) Loop runs n times so worst case can be Theta(n) times. Current case is similar to case c) but in previous case the size of array is always constant but here it vary with value i.

e) take n =16

i = n = 16

every time i is divided by 2 and updated so loop runs 5 times until i>0, which is equal to (log n)base 2 + 1 times

Here if n =16 ,then log 16 base = log 2^4 base 2= 4 log2 base 2 = 4

Finally 4+1 = 5 times

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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