Question 4: Find the complexity of the following blocks of code or algorithm's description. [Note: your answer must show the steps that lead to your final answer] 1) count = 0 for i = 1 to n do for k...


hi can you help


Question 4:<br>Find the complexity of the following blocks of code or algorithm's description.<br>[Note: your answer must show the steps that lead to your final answer]<br>1) count = 0<br>for i = 1 to n do<br>for k = 1 to n do<br>2)<br>for i = 1 to n do<br>count += i<br>count = 1<br>for (j = 2;j<n;j *= 2)<br>count = i +k + j;<br>for k = 1 to n do<br>count *= k<br>end for<br>k +=2<br>while j< n do<br>count +=j<br>j*= 2;<br>end while<br>The algorithm solves the problem<br>of size n by recursively solving<br>sub-problems of size n – 1, and<br>then combining the solutions in<br>Q(n) time.<br>end for<br>end for<br>3) The algorithm solves the problem of 4)<br>size n by dividing it into 64 sub-<br>problems of size n/8, recursively<br>solving each sub-problem, and then<br>combining the solutions in O(n?)<br>time<br>5) The algorithm solves the problem<br>by breaking it into 8 sub-problems<br>of 1/4 the scale, recursively solving<br>each sub-maze, and then<br>combining the solutions in linear<br>time<br>

Extracted text: Question 4: Find the complexity of the following blocks of code or algorithm's description. [Note: your answer must show the steps that lead to your final answer] 1) count = 0 for i = 1 to n do for k = 1 to n do 2) for i = 1 to n do count += i count = 1 for (j = 2;j< n="" do="" count="" +="j" j*="2;" end="" while="" the="" algorithm="" solves="" the="" problem="" of="" size="" n="" by="" recursively="" solving="" sub-problems="" of="" size="" n="" –="" 1,="" and="" then="" combining="" the="" solutions="" in="" q(n)="" time.="" end="" for="" end="" for="" 3)="" the="" algorithm="" solves="" the="" problem="" of="" 4)="" size="" n="" by="" dividing="" it="" into="" 64="" sub-="" problems="" of="" size="" n/8,="" recursively="" solving="" each="" sub-problem,="" and="" then="" combining="" the="" solutions="" in="" o(n?)="" time="" 5)="" the="" algorithm="" solves="" the="" problem="" by="" breaking="" it="" into="" 8="" sub-problems="" of="" 1/4="" the="" scale,="" recursively="" solving="" each="" sub-maze,="" and="" then="" combining="" the="" solutions="" in="" linear="">

Jun 04, 2022
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here