Question 3: (10 marks) Find the complexity of the following blocks of code or algorithm's description....

Transcribed Image Text:

Question 3: (10 marks) 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] (2 marks each) 1) count = 1 for i = 1 2) count = 0 for i = 1 to n do for k = 1 to n do for (j = 2;j<n; j*= 2) to 100 do count += i end for for k = 1 to 100 do count = i+ k + j; count *= k end for end for while j< n do count +=j j*= 2; end while end for end for 3) 4) The algorithm solves the problem of size n by dividing it into 8 subproblems of size n/2, recursively solving each sub- problem, and then combining the solutions in The algorithm solves the problem by breaking it into 4 sub-problems of 1/2 the scale, recursively solving each sub-maze, and then combining the solutions in linear time O(n³) time The algorithm solves the problem of size n by recursively solving two sub-problems of size n- 1, and then combining the solutions in constant time. 5) Question 3: (10 marks) 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] (2 marks each) 1) count = 1 for i = 1 2) count = 0 for i = 1 to n do for k = 1 to n do for (j = 2;j<n; j*= 2) to 100 do count += i end for for k = 1 to 100 do count = i+ k + j; count *= k end for end for while j< n do count +=j j*= 2; end while end for end for 3) 4) The algorithm solves the problem of size n by dividing it into 8 subproblems of size n/2, recursively solving each sub- problem, and then combining the solutions in The algorithm solves the problem by breaking it into 4 sub-problems of 1/2 the scale, recursively solving each sub-maze, and then combining the solutions in linear time O(n³) time The algorithm solves the problem of size n by recursively solving two sub-problems of size n- 1, and then combining the solutions in constant time. 5)

Answer rating: 100% (QA)

O ouhilb j masters Hheorem St... View the full answer