Question

4. [16 marks total (6 marks each)] Do a worst-case analysis for the following algorithm segments, counting the number of multiplications which occur. I have marked the lines with the multiplications you are to count with ). For all of these algorithms, use n as your fixed input size (even though n doesn't really represent the "size" of the input). Be sure to include an explanation with your answers to obtain full marks. (a) t-10; for (i-1;in-H) t-5*t; (b) (For this algorithm segment you can assume that n is greater than or equal to 4, and n is a power of 2, i.e. n-2k for some k-2, 3..) for (k-1; k< (n-2); k++)( p-n; while (p > 1) t a-a*10; ) p-lp/2); (c) answer -4; for (i-l; i<n; it+) for (G-1;j n;j+)! for (k-1;k< 2i kH) answer-answer *10;*

Answer 1

4)
a)
worst case complexity:O(n^2)
explanation:
   outer loop runs for n-1 times
   inner loop runs for i+3 for each iteration of i
let i=1, inner loop runs 1+3 times
let i=2, inner loop runs 2+3 times
,
,
,
let i=n-1, inner loop runs n-1+3 times
total : 1+3 + 2+3 + 3+3 + ,,,,,, + n-1 +3 = (1+2+3+,,+n-1)+3*(n-1)= n*(n-1)/2 + 3*(n-1) = O(n^2) times
so multiplication will be performed :O(n^2)

b)
worst case complexity :O(nlogn)
outer loop runs n-2 times
inner loop runs logn times for each iteration of outer loop
total complexity : (n-2) *logn = O(nlogn)
so multiplication will be performed :O(nlogn)

c)
worst case complexity :O(n^3)
outer loop runs n times
inner middle loop runs n times
inner most loop runs n*2i times for each i of outer loop
for i=1 inner most loop runs n*2*1 times
for i=2 inner most loop runs n*2*2 times
for i=3 inner most loop runs n*2*3 times
,
,
for i=n inner most loop runs n*2*n times
total complexity : n*2*1 +n*2*2 +,,, + n*2*n = n*2*(1+2+3+,,,+n) = n*2*(n*(n+1))/2 = O(n^3)