Answer to Question #247207 in Discrete Mathematics for Alina

Question

What is the big-O estimate of the function given in the pseudocode below if the size of the input is n? (a function that takes in a list of numbers as input and returns the biggest number) Justify your answer.

define function(input_list):

for i from range 0 to length(input_list):

min_idx = i

for j from range item+1 to length(input_list):

if input_list[min_idx] > input_list[j]:

min_idx = j

input_list[i], input_list[min_idx] = input_list[min_idx], input_list[i]

return input_list[length(input_list)]

Answer 1

If the time it takes to execute a method is proportional to the square of the input size, it has quadratic time complexity.... for(var I = 0; I length; i++) /has a temporal complexity of O(n) for (var j = 0; j length; j++) /has an O(n2) time complexity /