Characterize the asymptotic growth of the worst-case time complexity of the algo
ID: 3574455 • Letter: C
Question
Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer.
Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer.
Exercise 12.3.3: Worst-case time complexity finding the maximum value of a function. The function M takes three input values that are positive integers and outputs a positive integer. We don't know much about the function Mbut we are given some instructions to compute M. The line assume that it takes O(1) operations to compute the value of Mon any input. The input to the algorithm is a sequence of n numbers. We would like to find the maximum value of the function M where the three input values are numbers from the sequence. Numbers can be repeated, so M (a1, a1, a1) is a possibility. FindMaxFunctionValue Input: a1, a2,...,an n, the length of the sequence. Output: The largest values of M on input values from the sequence max M (a1, a1, a1) For 1 to n For 1 ton Fork 1 ton new Mai, ai, ak If (new max), max new End-for End-for End-for Return( max) Characterize the asymptotic growth of the worst-case time complexity of the algorithm. Justify your answer.Explanation / Answer
It is given that M function take O(1) time to calculate the value. In the algorithm have a three loops. Each going from 1 to n.So each loop iterates n times but as they are nested. The total number of the times the statements inside the third loop are executed is n*n*n times. As the operations inside the third loop only take unit time. The total time taken by the algorithm will be O(n^3).